우체국
시간 제한2초메모리 제한128 MB
마을 좌표와 주민 수가 주어질 때, 전체 주민까지 거리의 합을 최소화하는 가장 작은 좌표(가중 중앙값)를 구합니다.
문제
수직선 위에 N개의 마을이 있다. i번째 마을은 좌표 X[i]에 있고, A[i]명이 살고 있다.
마을들을 위해 우체국 하나를 세우려고 한다. 우체국의 위치는 모든 사람과 우체국 사이 거리의 합이 최소가 되도록 정한다. 이때 우체국을 세울 위치를 구하라.
거리의 합은 마을 단위가 아니라 각 사람 단위로 계산한다는 점에 유의하라.
입력
첫째 줄에 마을의 수 N(1 ≤ N ≤ 100,000)이 주어진다.
다음 N개의 줄에 각 마을의 좌표 X[i]와 거주 인원 A[i]가 한 줄에 하나씩 주어진다. 모든 값은 정수이며, |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000이다.
모든 A[i]의 합은 0보다 크다.
출력
첫째 줄에 우체국을 세울 위치를 출력한다. 답이 여러 개이면 그중 가장 작은 위치를 출력한다.