|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
The difference between this problem and "Colors II" is in bold.
There are $n$ points on the plane. Each of these points has been assigned a certain color, but not that all points are of the same color. Determine the largest possible (Euclidean) distance between any pair of different-colored points. All these points lie on a straight line.
Input
The first line of the input contains a single integer $n$ $(2 \le n \le 250 000)$. Each of the following $n$ lines describes a single point. A point's description consists of three integers $x_i$, $y_i$ and $c_i$ $(-10^9 \le x_i, y_i \le 10^9, 1 \le c_i \le n)$ separated by single spaces; the numbers $x_i$ and $y_i$ are the $i$-th point's coordinates, and $c_i$ is the id of the point's color.
There are at least two different colors and no two points have the same coordinates.
It is guaranteed that all $n$ points lie on a straight line.
Output
The first and only line of the output should contain the square of the maximum distance between two points of different colors.
Sample test(s)
Input
3
0 0 1
1 1 2
2 2 1
Output
2