time limit per test: 0.25 sec.
memory limit per test: 4096 KB
Every city in Berland is situated on Ox axis. The government of the country decided to build new telecasting station. After many experiments Berland scientists came to a conclusion that in any city citizens displeasure is equal to product of citizens amount in it by distance between city and TV-station. Find such point on Ox axis for station so that sum of displeasures of all cities is minimal.

Input

Input begins from line with integer positive number N (0<N<15000) – amount of cities in Berland. Following N pairs (X, P) describes cities (0<X, P<50000), where X is a coordinate of city and P is an amount of citizens. All numbers separated by whitespace(s).

Output

Write the best position for TV-station with accuracy 10-5.

Sample Input

4
1 3
2 1
5 2
6 2

Sample Output

3.00000

题意：

百慕大的每一座城市都坐落在一维直线上,这个国家的政府决定建造一个新的广播电视台。
经过了许多次试验后，百慕大的科学家们提出了一个结论:在每座城市的不满意度等于这座城市的市民数与这座城市与广播电视台的距离的乘积.
你需要找到这个一维直线上的一点来建造广播电视台，使得所有城市的不满意度的和最小.
注意!!!这道题有Special Judge 如样例答案也可以为2.00000

题解：

暴力的方法就是枚举中间的每一个点，然后找到最小的，这样可以变成O(n^2)。
但N有15000那么大，所以暴力不可取。
那么我们怎么做呢，看似怎么也没办法做啊！
其实这道题是加权中位数。
在信息学竞赛中，有这样一类题，给出了若干个排列在一条直线上的点，每个点有一个权值，比如说货物量、人数什么的，然后让我们找出使所有点的货物、人集合到一个点的总代价最小的位置。我们将会发现，这一类问题实际上就是带权中位数问题。
以下内容摘抄自《算法导论》：
对分别具有正权重ω1, ω2, …, ωn, 且满足   

的n个互异元素x1, x2, … , xn 来说，带权中位数xk（较小中位数）是满足如下条件的元素：

和

例如，如果元素是0.1， 0.35， 0.05, 0.1, 0.15, 0.05, 0.2, 并且每个元素的权重等于本身（即对所有i=1, 2, … , 7, 都有wi = xi），那么中位数是0.1， 而带权中位数是0.2。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int s[23333];
struct qer
{
    int pos, val;
}num[23333];
bool cmp(qer a, qer b)
{
    return a.pos < b.pos;
}
int main()
{
    int n, W = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &num[i].pos, &num[i].val);
    sort(num + 1, num + n + 1, cmp);
    for (int i = 1; i <= n; i++)
    {
        W += num[i].val;
        s[i] = W;
    }
    for (int i = 1; i <= n; i++)
        if (s[i] >= W/2)
        {
            cout << num[i].pos << ".0000";
            break;
        }
    return 0;
}