×

EASY

Cross product

# 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 put
d1 = 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

This question is marked "community wiki".

6.7k62119138
accept rate: 12%

19.8k350498541

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

(24 Aug '12, 22:51)

 1 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 16.9k●49●115●225 accept rate: 11% @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)
 1 For T = 1000 and N=1000 we have N^3. That's the reason why I didn't post the pure N^2 solution but combined it with convex hull (although worst case is still N^3), which gave me runtime error. Does this mean that we should NEVER take into account the number of test cases ?? answered 23 Jul '12, 00:20 4★lazzrov 136●1●1●8 accept rate: 0% 1 But sum of Ns in test input is <= 5000, so T = 1000 and N = 1000 is not possible. Did I missed something in your question? (23 Jul '12, 00:24) 2 You forget about constraint: sum of all N in test file <=5000. So the worst test case is 5 tests with N=1000 which is totally fine for O(N^2) solution. (23 Jul '12, 00:25) Thanks, that clears it up :) (23 Jul '12, 00:29) lazzrov4★
 0 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 4★gareve 1 accept rate: 0%
 0 To check whether the points A3 A4 are on the opposite side or same side of line A1A2, i am putting the points A3 and A4 in the equation of line A1A2 and then checking the sign.. But this method gives wrong answer on submission.. whereas if i use the cross product method as given in editorials, i got my code accepted. Can you please tell me , what's wrong with my first method ? answered 23 Jul '12, 12:38 46●4 accept rate: 0% 1 Can you describe what you think this statement calculates? tmp2=a[i][1]-m*a[i][0]-c It seems to me, that you are calculating Ay = m * Ax - c and I see that m is something like angle, but I'm lost what c stands for... (23 Jul '12, 13:56) 1 equation of line is of form y=mx+c; here m is the slope which is calculated as m = (y2-y1)/(x2-x1) where (x1,y1) and (x2,y2) are any two point lying on this line. c is calculated by putting (x1,y1) in the equation of line as : c = y1-mx1; now for any two points (x3,y3) and (x4,y4) say d3=y3-mx3-c and d4=y4-mx4-c ; if (x3,y3) and (x4,y4) lies on opposite side of line , d3 and d4 will have opposite sign and if they lie on same side of line d3 and d4 will have same sign. tmp2 is analogous to d ; a[i][1] stores ith y coordinate , a[i][0] stores ith x coordinate (24 Jul '12, 00:55)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×3,820
×647
×9

question asked: 23 Jul '12, 00:03

question was seen: 19,816 times

last updated: 25 Dec '12, 13:42