Testing Your Geometry Template#12860

Testing Your Geometry Template (Editorial)

Firstly, let's look at two points with coordinates (x_1, y_1) and (x_2, y_2) with x_1 \neq x_2. Where does perpendicular bisector to the segment between them intersect the -axis?

Let's say it's at point , then we must have (x_1-X)^2 + y_1^2 = (x_2-X)^2 + y_2^2, implying (x_1^2 + y_1^2) - (x_2^2 + y_2^2) = 2X(x_1-x_2), so X = \frac{(x_1^2 + y_1^2) - (x_2^2 + y_2^2)}{2(x_1-x_2)}

Now, we need to find the largest and smallest such values over all pairs (x_1, y_1), (x_2, y_2) of points from the statement with x_1 \neq x_2.

How to check if the largest value doesn't exceed ?

Note that it's equivalent to the following: (x_1^2 + y_1^2) - (x_2^2 + y_2^2) \le 2t(x_1-x_2) whenever x_1 > x_2, which is equivalent to (x_1^2 + y_1^2) - 2tx_1 \le (x_2^2 + y_2^2) - 2tx_2, when x_1<x_2.

Note that it's enough to check this inequality only for pairs (x_1, y_1), (x_2, y_2) such that there is no point (x_3, y_3) with x_1>x_3>x_2. Indeed, if the inequality holds for any two points with "adjacent" -coordinates, it would hold for any two points. So, let's check it only for them.

So we could say just "sort points by coordinate, find this for every pair of adjacent points with different coordinates, and take the largest of them". But everything is not so easy. What if we have many points with coordinate x_1 and many points with coordinate x_2? We would need to find this for every pair of them to check properly. But... would we?

Note that to maximize \frac{(x_1^2 + y_1^2) - (x_2^2 + y_2^2)}{2(x_1-x_2)} under fixed x_1, x_2 with x_1>x_2, we just have to maximize |y_1| and minimize |y_2|. So, the algorithm for finding the largest value of X = \frac{(x_1^2 + y_1^2) - (x_2^2 + y_2^2)}{2(x_1-x_2)} would go as follows: sort points by the -coordinate, in case of equality put points with bigger absolute value of coordinate first. Then, find this for every pair of adjacent points whose coordinates are different, and take the largest of them.

Similarly, find the smallest such , and take the difference between them.'