【HDOJ】4355 Party All the Time

  1 /* 4355 */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <algorithm>
 12 #include <cstdio>
 13 #include <cmath>
 14 #include <ctime>
 15 #include <cstring>
 16 #include <climits>
 17 #include <cctype>
 18 #include <cassert>
 19 #include <functional>
 20 #include <iterator>
 21 #include <iomanip>
 22 using namespace std;
 23 //#pragma comment(linker,"/STACK:102400000,1024000")
 24 
 25 #define sti                set<int>
 26 #define stpii            set<pair<int, int> >
 27 #define mpii            map<int,int>
 28 #define vi                vector<int>
 29 #define pii                pair<int,int>
 30 #define vpii            vector<pair<int,int> >
 31 #define rep(i, a, n)     for (int i=a;i<n;++i)
 32 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 33 #define clr                clear
 34 #define pb                 push_back
 35 #define mp                 make_pair
 36 #define fir                first
 37 #define sec                second
 38 #define all(x)             (x).begin(),(x).end()
 39 #define SZ(x)             ((int)(x).size())
 40 #define lson            l, mid, rt<<1
 41 #define rson            mid+1, r, rt<<1|1
 42 
 43 typedef struct {
 44     double x, w;
 45 } node_t;
 46 
 47 const double eps = 1e-4;
 48 const int maxn = 50005;
 49 node_t nd[maxn];
 50 int n;
 51 
 52 double calc(double x) {
 53     double ret = 0.0;
 54     
 55     rep(i, 0, n)
 56         ret += pow(fabs(x-nd[i].x), 3) * nd[i].w;
 57         
 58     return ret;
 59 }
 60 
 61 void solve() {
 62     double l = 1e7;
 63     double r = -1e7;
 64     double m1, m2;
 65     double tmp1, tmp2;
 66     
 67     rep(i, 0, n) {
 68         l = min(l, nd[i].x);
 69         r = max(r, nd[i].x);
 70     }
 71     
 72     while (fabs(r-l) > eps) {
 73         m1 = l + (r-l)/3;
 74         m2 = r - (r-l)/3;
 75         tmp1 = calc(m1);
 76         tmp2 = calc(m2);
 77         if (tmp1 < tmp2) {
 78             r = m2;
 79         } else if (tmp1 > tmp2) {
 80             l = m1;
 81         } else {
 82             l = r;
 83         }
 84     }
 85     
 86     double ans = calc(l);
 87     printf("%.0lf\n", ans);
 88 }
 89 
 90 int main() {
 91     ios::sync_with_stdio(false);
 92     #ifndef ONLINE_JUDGE
 93         freopen("data.in", "r", stdin);
 94         freopen("data.out", "w", stdout);
 95     #endif
 96     
 97     int t;
 98     
 99     scanf("%d", &t);
100     rep(tt, 1, t+1) {
101         scanf("%d", &n);
102         rep(i, 0, n)
103             scanf("%lf %lf", &nd[i].x, &nd[i].w);
104         printf("Case #%d: ", tt);
105         solve();
106     }
107     
108     #ifndef ONLINE_JUDGE
109         printf("time = %d.\n", (int)clock());
110     #endif
111     
112     return 0;
113 }