공평한 분배

시간 제한5초메모리 제한512 MB

요약

원점을 지나는 직선 하나로 가중치가 있는 n개의 점을 두 반평면으로 나눌 때, 두 반평면 가중치 합의 차이의 절댓값을 최소로 만드는 값을 구한다.

난이도: 어려움10점 중 8점
유형: 기하, 정렬, 투 포인터, 누적 합
정답자: 아직 제출이 없습니다

문제

과학자들이 그레이트빅토리아 사막에서 거대한 수원을 발견했다. 이 사막을 공유하는 두 주인 웨스턴오스트레일리아주와 사우스오스트레일리아주의 대표들은 수원을 공평하게 나누기로 합의했다. 이들은 수원의 위치를 지도에 표시하고, 지도 중앙을 지나는 직선을 그어 직선의 양쪽에 있는 수원을 각 주에 배정하기로 했다. 지도의 중앙은 $(0, 0)$ 에 있다.

한 주가 얻는 이득은 자기 쪽 반평면에 있는 수원의 가치 합에서 같은 반평면에 있는 인프라 개발 비용의 합을 뺀 값이다. 비용도 지도에 함께 주어진다. 두 주의 대표는 두 주가 얻는 이득의 차이를 최소로 하는 공평한 분배를 계산해 달라고 요청한다. 분할선은 어떤 위치도 직접 지나서는 안 된다.

입력

첫째 줄에 수원과 인프라 위치의 개수 $n$ 이 주어진다. ( $1 \le n \le 10^5$ )

다음 $n$ 개의 줄에는 세 정수 $x_i$ , $y_i$ , $v_i$ 가 주어진다. ( $-10^9 \le x_i, y_i, v_i \le 10^9$ ) 이는 $v_i \ge 0$ 이면 가치 $v_i$ 인 수원의 위치 $(x_i, y_i)$ 를, $v_i < 0$ 이면 개발 비용 $-v_i$ 인 인프라 위치를 나타낸다. 모든 위치는 서로 다르며 $(0, 0)$ 과도 다르다.

출력

두 주가 얻는 이득의 차이의 절댓값의 최솟값을 출력한다.

예제3

예제 1

입력

예상 출력

예제 2
입력
```
3
-1 -1 100
0 1 101
1 -1 102
```
예상 출력
```
99
```
예제 3
입력
```
5
1 1 5
1 0 5
1 -1 5
-1 0 15
-1 1 -2
```
예상 출력
```
2
```