### 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 **(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**can be calculated as

_{2}= (X_{2}, Y_{2})**dist(A**. So largest side of the tetragon

_{1}, A_{2}) = sqrt((X_{1}- X_{2})^{2}+ (Y_{1}- Y_{2})^{2})**(A**is the maximum between

_{1}, A_{2}, A_{3}, A_{4})**dist(A**,

_{1}, A_{2})**dist(A**,

_{2}, A_{3})**dist(A**,

_{3}, A_{4})**dist(A**. There is a way how to do this in one simple loop:

_{4}, A_{1})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**and

_{2}A_{3}**A**(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

_{4}A_{1}**A**. Similarly side

_{3}A_{4}**A**can intersect only with

_{2}A_{3}**A**and so on. Summarizing we see that the boundary of the tetragon does not cross itself if and only if segments

_{4}A_{1}**A**and

_{1}A_{2}**A**do not intersect and segments

_{3}A_{4}**A**and

_{2}A_{3}**A**do not intersect.

_{4}A_{1}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**be four points and we need to check whether line segments

_{4}= (X_{4}, Y_{4})**A**and

_{1}A_{2}**A**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

_{3}A_{4}**A**and

_{1}**A**lie at opposite sides of the line

_{2}**A**and the same for points

_{3}A_{4}**A**and

_{3}**A**and line

_{4}**A**. The main tool to check this condition is cross product of vectors.

_{1}A_{2}Denote by **DIRECTION(A, B, C)** for three points **A = (X _{A}, Y_{A})**,

**B = (X**,

_{B}, Y_{B})**C = (X**the value of cross product

_{C}, Y_{C})_{B}- X

_{A}) * (Y

_{C}- Y

_{A}) - (X

_{C}- X

_{A}) * (Y

_{B}- Y

_{A})**. Now put

dThen points **A_{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})

_{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**operations in worst case and usually computer can perform about

^{12}**10**such operations in a second.

^{6}-10^{7}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**. Line

_{i}A_{j}**A**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

_{i}A_{j}**X**and

**Y**. Then clearly segments

**XY**and

**A**do not intersect each other. Also it is impossible that segments

_{i}A_{j}**A**and

_{i}X**A**intersect each other as well as segments

_{j}Y**A**and

_{i}X**A**intersect each other. Hence either

_{j}Y**A**or

_{i}A_{j}XY**A**will be a correct tetragon which proves our assertion.

_{i}A_{j}YXFor **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 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 **A _{i}A_{j}** 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)