## SGU 114 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=114

## 114. Telecasting station

time limit per test: 0.50 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`

sigma(wi)(xi < xk) <= W/2
sigma(wi)(xi > xk) <= W/2

### CODE

```#include<stdio.h> #include<iostream> #include<algorithm> using namespace std;   struct node { double x; long long p; }D[15005];   bool cmp(node a,node b) { return (a.x<b.x); }   int main() { int n,i; scanf("%d",&n); for(i=0;i<n;i++){ scanf("%lf%lld",&D[i].x,&D[i].p); } sort(D,D+n,cmp); for(i=1;i<n;i++){ D[i].p+=D[i-1].p; } long long mid=D[n-1].p/2; for(i=0;i<n;i++){ if(D[i].p>=mid) break; } printf("%.5lfn",D[i].x); return 0; }```
» 本博客采用署名 2.5 中国大陆许可协议进行许可，本文版权归作者所有，欢迎转载，但必须在明显位置给出原文连接。