PROBLEM LINKDIFFICULTYEASY PREREQUISITESPROBLEMYou need to find the largest possible largest side of a simple quadrilateral with vertices from the given set of points in the plane. QUICK EXPLANATIONFor 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. EXPLANATIONAt 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 (A_{1}, A_{2}, A_{3}, A_{4}) 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 A_{i1}, A_{i2}, A_{i3}, A_{i4} 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 A_{1} = (X_{1}, Y_{1}) and A_{2} = (X_{2}, Y_{2}) can be calculated as dist(A_{1}, A_{2}) = sqrt((X_{1}  X_{2})^{2} + (Y_{1}  Y_{2})^{2}). So largest side of the tetragon (A_{1}, A_{2}, A_{3}, A_{4}) is the maximum between dist(A_{1}, A_{2}), dist(A_{2}, A_{3}), dist(A_{3}, A_{4}), dist(A_{4}, A_{1}). There is a way how to do this in one simple loop: res = 0 for i=1 to 4 res = max(res, dist(A_{i}, A_{i 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 A_{1}A_{2}. Clearly it can not intersect with sides A_{2}A_{3} and A_{4}A_{1} (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 A_{3}A_{4}. Similarly side A_{2}A_{3} can intersect only with A_{4}A_{1} and so on. Summarizing we see that the boundary of the tetragon does not cross itself if and only if segments A_{1}A_{2} and A_{3}A_{4} do not intersect and segments A_{2}A_{3} and A_{4}A_{1} 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 A_{1} = (X_{1}, Y_{1}), A_{2} = (X_{2}, Y_{2}), A_{3} = (X_{3}, Y_{3}), A_{4} = (X_{4}, Y_{4}) be four points and we need to check whether line segments A_{1}A_{2} and A_{3}A_{4} 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 A_{1} and A_{2} lie at opposite sides of the line A_{3}A_{4} and the same for points A_{3} and A_{4} and line A_{1}A_{2}. The main tool to check this condition is cross product of vectors. Denote by DIRECTION(A, B, C) for three points A = (X_{A}, Y_{A}), B = (X_{B}, Y_{B}), C = (X_{C}, Y_{C}) the value of cross product d_{1} = DIRECTION(A_{1}, A_{3}, A_{4}) d_{2} = DIRECTION(A_{2}, A_{3}, A_{4}) d_{3} = DIRECTION(A_{3}, A_{1}, A_{2}) d_{4} = DIRECTION(A_{4}, A_{1}, A_{2})Then points A_{1} and A_{2} lie at opposite sides of the line A_{3}A_{4} if and only if d_{1} and d_{2} are of different sign. One of the popular way to check this is to check condition d_{1} * d_{2} < 0. But be careful, in this problem the product d_{1} * d_{2} do not fit in standard 32bit integer type. So if you choose this way then cast d_{1} to 64bit integer type before multiplication. More safe way is to check condition (d_{1} < 0 and d_{2} > 0) or (d_{1} > 0 and d_{2} < 0). Similarly we need also to check that d_{3} and d_{4} 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(N^{4}) which is too slow since it requires about 10^{12} operations in worst case and usually computer can perform about 10^{6}10^{7} 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 A_{i}A_{j} can be a side of some tetragon. Consider some segment A_{i}A_{j}. Line A_{i}A_{j} divides the plain into two open halfplanes. Each of the remaining points lies at one of these halfplanes since no point lie on the line itself. By pigeonhole principle at least two of the remaining points belong to the same halfplane (there are at least 3 remaining points and only 2 halfplanes). Denote these two points as X and Y. Then clearly segments XY and A_{i}A_{j} do not intersect each other. Also it is impossible that segments A_{i}X and A_{j}Y intersect each other as well as segments A_{i}X and A_{j}Y intersect each other. Hence either A_{i}A_{j}XY or A_{i}A_{j}YX 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(A_{i}, A_{j})) Obtained algorithm has complexity O(N^{2}) 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 SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here. RELATED PROBLEMSIntersection (SPOJ 8149 LINESEG)
This question is marked "community wiki".
asked 23 Jul '12, 00:03

I really like this one ;) Was it meant to get TLE when using sort when n > 4? IMHO worst case is 5 * n * log(n), where n = 1000 what should get AC for 2 seconds time limit, right? answered 23 Jul '12, 00:09
@betlista I have done sorting of all distances and then for all line in descending order of length i find if there are atleast two points on either its left or right side. First line is the answer. I am getting WA and not TLE. so it would be within the timelimit. Please see the code and help me get my mistake. link is http://www.codechef.com/viewsolution/1281573
(25 Aug '12, 21:24)

A simpler solution without see n=4 as a special case(setter and tester solution), is to test all the sides(O(n^2)) and see if there are at least 2 points in one of the sides(cross>0 or cross<0) of the segment. Because there are no collinear points, this third "for" validates in at most 5 steps. So the solution remains O(n^2) and simpler to code. answered 23 Jul '12, 01:40

I have done sorting of all distances and then for all line in descending order of length i find if there are atleast two points on either its left or right side. First line is the answer.
Please see the code and help me get my mistake. link is http://www.codechef.com/viewsolution/1281573