题干：

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

题目大意：

n个城市，第i个城市坐标为x[i]，人口为p[i]，现在要建立一个电视台，使得各个城市到电视台的距离乘以该城市人口之和最小。

解题报告：

可以这样来简单考虑：若各个城市人口均为1，则问题就是求城市坐标的中位数。现在人口为p，则可以看做是有p个人口为1的城市，这样就把问题转化为求中位数。

AC代码：

#include <iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
#define LL long long
struct city
{
    double x,p;
}c[50005];
bool cmp(city a,city b)
{
    return a.x<=b.x;
}
int main()
{
    int n;
    scanf("%d",&n);
    double sum=0.0;
    for(int i=0;i<n;++i)
    {
        scanf("%lf%lf",&c[i].x,&c[i].p);
        sum+=c[i].p;
    }
    double s=0.0;
    sort(c,c+n,cmp);
    for(int i=0;i<n;++i)
    {
        s+=c[i].p;
        if(s-sum/2>=1e-10) {printf("%.10lf\n",c[i].x);break;}
    }
    return 0;
}

三分的代码：（但是怎么能保证都是整数呢？题目爬去不到了，，也交不了试试）

#include <bits/stdc++.h>
#define max(a,b) ((a)>(b))?(a):(b)
#define min(a,b) ((a)>(b))?(b):(a)
#define rep(i,initial_n,end_n) for(int (i)=(initial_n);(i)<(end_n);i++)
#define repp(i,initial_n,end_n) for(int (i)=(initial_n);(i)<=(end_n);(i)++)
#define eps 1.0E-8
#define MAX_N 1010
#define INF 1 << 30
using namespace std;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef long long ll;
typedef unsigned long long ull;
 
pii a[15010];
 
 int main() {
    int n;
    scanf("%d", &n);
    int minn = INT_MAX, maxx = INT_MIN;
    rep(i, 0, n) {
        scanf("%d%d", &a[i].first, &a[i].second);
        if(minn > a[i].first) minn = a[i].first;
        if(maxx < a[i].first) maxx = a[i].first;
    }
    double b = minn, e = maxx, m = (b+e)/2, mm = (m+e)/2;
    while(b - e < -eps) {
        double tmp = 0, tmpp = 0;
        rep(i, 0, n) {
            tmp += fabs(a[i].first - m) * 1.0 * a[i].second, tmpp += fabs(a[i].first - mm) * 1.0 * a[i].second;
        }
        if(tmp - tmpp < -eps) e = mm;
        else b = m;
        m = (b+e)/2, mm = (m+e)/2;
    }
    printf("%f\n", m);
    return 0;
 }