# SGU 114 - Telecasting station

## Description

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

 1 2 3 4 5  4 1 3 2 1 5 2 6 2 

## Sample Output

 1  3.00000 

## Analysis

• 最后精确到 $10^{-5}$ 的要求基本是多余的，只要在结果后面再输出“.00000”；
• 本题使用了 Special Judge，因此答案可能不唯一。

$$(1, 1)\quad (1, 2)\quad (1, 3)\quad (2, 4)\quad (5, 5)\quad (5, 6)\quad (6, 7)\quad (6, 8)$$

• 如果城市数目为奇数，那么我们所需要求的就是第 S / 2 + 1 个城市，其中 $S$ 表示城市总数；
• 如果城市数目为偶数，那么我们可以输出第 S / 2 个城市或第 S / 2 + 1 个城市。

## Solution

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44  #include #include #include using namespace std; struct City { City(int _P = 0, int _M = 0) { P = _P; M = _M; } int P, M; }; int cmp(City x, City y) { return x.P < y.P; } vector pCity; int main() { int N, P, M; while(cin >> N) { int nCnt = 0; pCity.clear(); for(int i = 1; i <= N; i++) { cin >> P >> M; pCity.push_back(City(P, M)); nCnt += M; } sort(pCity.begin(), pCity.end(), cmp); int nTmp = nCnt / 2 + 1; int nPos = 0; for(; nTmp > 0; nPos++) { if(nTmp - pCity[nPos].M > 0) { nTmp -= pCity[nPos].M; } else { break; } } cout << pCity[nPos].P << ".00000" << endl; } return 0; }