문제
2차원 평면에 K개의 색 중 하나가 칠해진 점이 N개 주어진다. i번째 점은 (xi, yi)에 있다.
거리가 최대가 되도록 색이 다른 점 2개를 골랐을 때, 두 점 사이의 거리 제곱을 구하여라.
입력
첫 번째 줄에 점의 개수를 의미하는 자연수 N과 색의 개수 K가 주어진다. (2 ≤ N ≤ 500,000, 2 ≤ K ≤ N)
두 번째 줄부터 N개의 줄에 점의 위치 (xi, yi)와 색의 정보 ci가 주어진다. (-109 ≤ xi, yi ≤ 109, 1 ≤ ci ≤ K)
출력
거리가 최대가 되도록 색이 다른 점 2개를 골랐을 때, 두 점 사이의 거리 제곱을 출력한다.
예제
9
-1 -1 1
3 -3 1
6 -6 3
-3 -6 2
12 0 3
3 4 2
-6 3 3
0 9 1
6 9 2
로그인해야 코드를 작성할 수 있어요.