PROBLEM LINK
DIFFICULTY
EASY
PREREQUISITES
PROBLEM
You need to find the largest possible largest side of a simple quadrilateral with vertices from the given set of points in the plane.
QUICK EXPLANATION
For the case N = 4 we can use naive approach. That is we can iterate over all permutations of given 4 vertexes and check that the boundary of obtained quadrilateral does not cross itself. For this we need to check only that opposite sides of the quadrilateral do not intersect. This is a standard computational geometry problem. This can be checked by checking signs of four cross products.
For N >= 5 the answer is always the distance between farthest pair of points since every segment with endpoints from the given set of points can be a side of some tetragon. Indeed, by the pigeonhole principle at least 2 of the remaining points lie on the same side of the line of this segment. Hence we can form simple polygon using these two points and considered segment. The farthest pair of points can be found by simple double loop.
EXPLANATION
At first let us consider in detail naive approach. According to the problem statement we need to consider all possible tetragons, find the largest side for each tetragon and find maximum among these largest sides.
To consider all tetragons we can iterate in four nested loops over all possible quadruples of different points (A1, A2, A3, A4) like this:
for i1=1 to N
for i2=1 to N
for i3=1 to N
for i4=1 to N
if i1!=i2 and i1!=i3 and i1!=i4 and i2!=i3 and i2!=i4 and i3!=i4
do something with Ai1, Ai2, Ai3, Ai4
For the chosen four points we at first need to check that the boundary of the quadrilateral with vertexes at these points do not cross itself. We will discuss how to do this a bit later.
If chosen points really form the tetragon we need to find its largest side. The distance between two points A1 = (X1, Y1) and A2 = (X2, Y2) can be calculated as dist(A1, A2) = sqrt((X1 - X2)2 + (Y1 - Y2)2). So largest side of the tetragon (A1, A2, A3, A4) is the maximum between dist(A1, A2), dist(A2, A3), dist(A3, A4), dist(A4, A1). There is a way how to do this in one simple loop:
res = 0 for i=1 to 4 res = max(res, dist(Ai, Ai mod 4 + 1))
The trick is to use mod operation.
Now let’s return back and learn how to check that the boundary of the tetragon does not cross itself. What does it mean here? Consider for example the side A1A2. Clearly it can not intersect with sides A2A3 and A4A1 (it follows from the condition that no three points from the given set lie at the same line). So it can intersect only with side A3A4. Similarly side A2A3 can intersect only with A4A1 and so on. Summarizing we see that the boundary of the tetragon does not cross itself if and only if segments A1A2 and A3A4 do not intersect and segments A2A3 and A4A1 do not intersect.
So we are now facing one of the basic computational geometry problems: checking whether two line segments have common point. You can find one of the good explanations with pictures of this problem here (see the first answer) or here (the same explanation but without pictures). But let’s discuss another way to check this. We will follow Chapter 33 of Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Let A1 = (X1, Y1), A2 = (X2, Y2), A3 = (X3, Y3), A4 = (X4, Y4) be four points and we need to check whether line segments A1A2 and A3A4 intersect each other. Recall that no three points from our set lie at the same line. This simplifies our task a bit. The only thing that we should check is that points A1 and A2 lie at opposite sides of the line A3A4 and the same for points A3 and A4 and line A1A2. The main tool to check this condition is cross product of vectors.
Denote by DIRECTION(A, B, C) for three points A = (XA, YA), B = (XB, YB), C = (XC, YC) the value of cross product
**(B - A) x (C - A) = (XB - XA) * (YC - YA) - (XC - XA) * (YB - YA)**. Now putd1 = DIRECTION(A1, A3, A4) d2 = DIRECTION(A2, A3, A4) d3 = DIRECTION(A3, A1, A2) d4 = DIRECTION(A4, A1, A2)Then points **A1** and **A2** lie at opposite sides of the line **A3A4** if and only if **d1** and **d2** are of different sign. One of the popular way to check this is to check condition **d1 * d2 < 0**. But be careful, in this problem the product **d1 * d2** do not fit in standard 32bit integer type. So if you choose this way then cast **d1** to 64bit integer type before multiplication. More safe way is to check condition **(d1 < 0 and d2 > 0) or (d1 > 0 and d2 < 0)**. Similarly we need also to check that **d3** and **d4** are of different sign. We refer to the "Introduction to Algorithms" for further discussions related to this problem. There you can find the proof of this method and modification of this method that allows to deal with arbitrary four points that can lie at one line or even can coincide.
Thus we are now able to solve this problem in time O(N4) which is too slow since it requires about 1012 operations in worst case and usually computer can perform about 106-107 such operations in a second.
Now let’s follow our intuition. The most wanted thing here is to print the largest possible distance between pair of points hoping that this segment really can be a side of a tetragon. And in fact it is almost always correct. Let’s prove that for N >= 5 this is correct. In fact we will prove that for N >= 5 every segment AiAj can be a side of some tetragon. Consider some segment AiAj. Line AiAj divides the plain into two open half-planes. Each of the remaining points lies at one of these half-planes since no point lie on the line itself. By pigeonhole principle at least two of the remaining points belong to the same half-plane (there are at least 3 remaining points and only 2 half-planes). Denote these two points as X and Y. Then clearly segments XY and AiAj do not intersect each other. Also it is impossible that segments AiX and AjY intersect each other as well as segments AiX and AjY intersect each other. Hence either AiAjXY or AiAjYX will be a correct tetragon which proves our assertion.
For N = 4 this is not true in general. The simplest example is the set of square vertexes: (0, 0), (1,0), (1, 1), (0, 1). The largest distance here is sqrt(2) between points (0, 0) and (1, 1). On the other hand the only possible tetragon here is the square itself which has the largest side equals to 1.
Now combining all together we obtain the following fast enough algorithm to solve the problem. For N = 4 we use naive approach described above. For N >= 5 we simply find the farthest pair of points and print the distance between them. That is, in two nested loops we iterate over all unordered pairs of points find the distance between them and update the answer if necessary:
res = 0
for i=1 to N
for j=i+1 to N
res = max(res, dist(Ai, Aj))
Obtained algorithm has complexity O(N2) which is totally fine for the given time limit. The final suggestion is to calculate squares of distances which are integers in this loop and take square root only before printing the answer.
Note that the distance between farthest pair of points can be found even in O(N * log N). You can find this method in the textbook “Computational Geometry: An Introduction” by Franco P. Preparata, Michael Ian Shamos in section 4.2.3. Shortly the algorithm is the following. At first we find in O(N * log N) time the convex hull of the given set of points and then in O(N) time using method of two moving pointers find the diameter of the convex polygon.
SETTER’S SOLUTION
Can be found here.
Setter used almost the same approach described above. The only difference is that for N = 4 he used another way to iterate over all quadruples of points. He noted that each such quadruple is a permutation of the given set. So he iterates over all permutations using next_permutation routine. See his solution for further details.
TESTER’S SOLUTION
Can be found here.
Tester used another approach for N = 4. He iterates over all pair of points. For the given pair of points A and B he counts how many points from the given set lie at each side of the line AB. If both sides have points then he rejects this pair, otherwise he update the answer by dist(A, B) since clearly segment AB can be a side of some tetragon. At first sight this approach seems to be faulty since even if the remaining points C and D lie at the opposite sides of the line AB, segments AB and CD could not intersect so either ABCD or ABDC is a correct tetragon and we must update the answer by dist(A, B). But in fact if it happens that AB and CD do not intersect but C and D lie at opposite sides of the line AB then each of the 6 segments AiAj can be a side of some tetragon and what is the most curious AB will not be the largest segment. So absence of the update of answer by dist(A, B) will not effect to the final answer. We leave this as an exercise to the reader to prove that this is correct.
RELATED PROBLEMS
Intersection (SPOJ 8149 LINESEG)
Intersecting Line Segments (UVA 866)
Squares (ACM-ICPC Live Archive 4728)
