Post Office
Time limit2sMemory limit128 MB
Given village coordinates and resident counts, find the smallest position minimizing total weighted distance to all residents (weighted median).
- Level
Medium4 of 10
- Topics
- Sorting, Prefix sum, Math
- Solved
- No attempts yet
Problem
There are N villages on a number line. The i-th village is at coordinate X[i] and has A[i] residents.
You need to build one post office for these villages. Choose a position that minimizes the sum of the distances from the post office to every resident. Determine such a position.
The distance sum is computed over individual residents, not over villages.
Input
The first line contains the number of villages N (1 ≤ N ≤ 100,000).
Each of the next N lines contains the coordinate X[i] of a village and its number of residents A[i]. All values are integers, with |X[i]| ≤ 1,000,000,000 and 0 ≤ A[i] ≤ 1,000,000,000.
The sum of all A[i] is greater than 0.
Output
Print the position where the post office should be built. If there are multiple optimal positions, print the smallest one.