파리의 밤
시간 제한15초메모리 제한512 MB
일반 위치에 있는 등급이 매겨진 점 N개가 주어질 때, 두 경계 지점을 지나는 직선으로 나머지를 양쪽으로 나누어 두 합의 차의 최솟값을 구한다.
문제
SWERC 참가차 파리에 온 Morgane은 방문한 모든 기념비에 점수를 매겼다. 이번 주 마지막 밤에 그녀는 열기구를 타고 파리 시내를 180° 파노라마 사진 두 장으로 찍어 완벽한 360° 전경을 얻으려 한다. 그녀는 두 사진이 서로 비슷하게 잘 나오기를 바란다.
그래서 그녀는 다음과 같이 진행한다. 두 기념비를 골라 경계 기념비라 부르고, 열기구 조종사에게 이 두 기념비 사이로 이동해 달라고 요청한다. 그곳에서 180° 사진 두 장을 찍는데, 각 사진은 파리의 한쪽 면을 담고 두 면은 두 경계 기념비로 구분된다. 각 사진은 점수를 받으며, 그 점수는 사진에 담긴 기념비들의 점수 합이다. 경계 기념비는 두 사진 모두에 포함된다. 사진의 점수가 A와 B일 때 Morgane의 목표는 A와 B의 차이(절댓값)를 최소화하는 것이다.
열기구에서의 시야는 좋아서 모든 기념비가 두 사진 중 어느 쪽에서든 보인다.
Morgane이 적절한 경계 기념비를 고르도록 도와야 한다. 이를 위해 기념비 목록이 주어진다. Morgane이 방문한 각 기념비마다 목록에는 기념비 위치의 직교 좌표와 그 기념비의 점수를 나타내는 줄이 있다. Morgane이 찍을 수 있는 모든 사진 쌍 중에서 두 사진 점수 차이의 최솟값을 구하라.
입력
입력은 여러 줄로 이루어지며, 각 줄은 공백 하나로 구분된 정수들로 구성된다.
- 첫째 줄에는 기념비의 수 N이 주어진다.
- 다음 N개 줄에는 각 기념비에 대한 세 정수, 즉 X 좌표, Y 좌표, 점수 G가 주어진다.
출력
출력은 한 줄로 이루어지며, Morgane이 찍을 수 있는 사진 쌍의 점수 차이(절댓값)의 최솟값을 정수로 출력한다.
제한
- 2 ≤ N ≤ 4 000;
- 0 ≤ X,Y ≤ 1 000 000 000이고 1 ≤ G ≤ 1 000 000 000이다.
힌트
Morgane이 모든 기념비의 위치를 아주 정확히 파악했기 때문에, 세 기념비가 같은 직선 위에 있는 경우는 없다.