SGU114-Telecasting station - c++编程基础

114. Telecasting station

time limit per test: 0.5 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 amount of cities in Berland. Following N pairs (X, P) describes cities (0 , 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

题意是说，有个国家的城市之间要建个公交（我英语不好、翻译可能会跑偏、也可能是电视塔、也可能是别的、我也不知道是啥），然后有一个不满意度，咱们自己想想也知道，肯定都喜欢把地铁站设在自己家门口。然后这个不满意度=城市的人数*这个站的位置。。。然后的然后、我也不会做这个题，直接上理论：数学家说，这是一个带权中位数问题，具体内容见 http://baike.baidu.com/link url=NZbFTsJCCn_jsx8W24aLu6XGEVdpDH0hpO_SIzeCF7vFi_Nz-xV4pe7tzuJBpQsQSzoa719FmHYb3lr7QKV3q_ 这个讲的很明白了。然后，下面的代码就自然手到擒来了！！！

#include
      
       
#include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #include
                 #include
                 
                   #include
                  
                    using namespace std; struct N { double x; int p; } a[15009]; int b[15009]; int cmp(N a,N b) { return a.x
                   
                    =mid) { w=i; break; } } printf("%d\n",a[w].x); } return 0; }