xtu summer individual-4 B - Party All the Time

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #define LL long long
13 #define INF 0x3f3f3f3f
14 using namespace std;
15 const int maxn = 50010;
16 const double exps = 1e-7;
17 int n;
18 double x[maxn],w[maxn];
19 double test(double px){
20     double sum = 0;
21     for(int i = 0; i < n; i++)
22         sum += fabs(px-x[i])*fabs(px-x[i])*fabs(px-x[i])*w[i];
23     return sum;
24 }
25 int main(){
26     int t,i,j,k = 1;
27     double low,high,mid,midd;
28     scanf("%d",&t);
29     while(t--){
30         scanf("%d",&n);
31         low = INF;
32         high = -INF;
33         for(i = 0; i < n; i++){
34             scanf("%lf %lf",x+i,w+i);
35             low = min(low,x[i]);
36             high = max(high,x[i]);
37         }
38         while(fabs(high - low) >= exps){
39             mid = (high+low)/2.0;
40             midd = (high+mid)/2.0;
41             if(test(mid)+exps < test(midd))
42                 high = midd;
43             else low = mid;
44         }
45         printf("Case #%d: %.0f\n",k++,test(low));
46     }
47     return 0;
48 }