Sgu/114

求中位数.很容易证明若把"人数"看成"城市坐标"的"数据重复次数",全部数据的中位数可以为所求.若全部数据数量为偶数,中间两个数限制的闭区间内都可以成为解.

//P*M
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n, s = 0, s1 = 0;
double x1, x2;
struct reca{
  double x;
  int p;
};
reca a[20000];
bool operator <(reca a, reca b){
  return a.x < b.x;
}
int main(){
  freopen("sgu114.in", "r", stdin);
  freopen("sgu114.out", "w", stdout);
  scanf("%d", &n);
  for(int i = 1; i <= n; i++){
    scanf("%lf %d", &a[i].x, &a[i].p);
    s += a[i].p;
  }
  sort(a+1, a+1+n);
  s /= 2;
  s++;
  for(int i = 1; i <= n; i++){
    s1 += a[i].p;
    if(s1 >= s){printf("%lf\n", a[i].x); break;}
  }
  fclose(stdin);
  fclose(stdout);
  return 0;
}
<\source>