Telecasting station

Problem 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

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
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>

int main () {
std::ios::sync_with_stdio(false);

int n;
std::cin >> n;

double p_left = 0;
double p_right = 0;
double s_left = 0;
double s_right = 0;

std::vector<std::pair<double, double>> cities(n, std::pair<double, double>());
for(auto& city : cities) {
std::cin >> city.first >> city.second;
}

std::sort(cities.begin(), cities.end(), [](std::pair<double, double> a, std::pair<double, double> b) {
return a.first < b.first;
});

for(int i = 0; i < n; i++) {
p_right += cities[i].second;
s_right += cities[i].first * cities[i].second;
}

double sum = LONG_LONG_MAX;
double index = cities[0].first;

for(int i = 0; i < n - 1; i++) {
p_right -= cities[i].second;
p_left += cities[i].second;
s_right -= cities[i].first * cities[i].second;
s_left += cities[i].first * cities[i].second;
double a = cities[i].first * (p_left - p_right) + (s_right - s_left);
double b = cities[i + 1].first * (p_left - p_right) + (s_right - s_left);
if(sum - a > 1e-8) {
sum = a;
index = cities[i].first;
}

if(sum - b > 1e-8) {
sum = b;
index = cities[i + 1].first;
}
}

std::cout<<std::setiosflags(std::ios::fixed);
std::cout<<std::setprecision(5) << index << std::endl;

return 0;
}