二分，單獨(dú)判溢出的情況
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 using namespace std;
5
6 #define maxn 60000
7 struct node{
8 int b, h, w, d;
9 void in(){
10 scanf("%d %d %d %d",&b, &h, &w, &d);
11 }
12 }cistern[maxn];
13
14 void checkmin(double & x, double y){if(x > y)x = y;}
15
16 void checkmax(double & x, double y){if(x < y)x = y;}
17
18 int n, volumn;
19
20 double calc(double x){
21 double ans = 0;
22 for(int i = 0; i < n; i++){
23 if(cistern[i].b > x)continue;
24 ans += min( x - cistern[i].b , cistern[i].h*1.0 ) * cistern[i].d * cistern[i].w;
25 }
26 return ans;
27 }
28
29 double b_search(double l ,double r){
30 while(r - l > 1e-8){
31 double mid = (l + r)/2;
32 if(calc(mid) >= volumn )r = mid; else l = mid;
33 }
34 return ( r + l ) / 2;
35 }
36
37 int main(){
38 //freopen("in","r",stdin);
39 int testcase;
40 scanf("%d",&testcase);
41 while(testcase--){
42 scanf("%d",&n);
43 double l, r;
44 r = 0, l = 1e100;
45 for(int i = 0; i < n; i++)
46 {
47 cistern[i].in();
48 checkmax( r, cistern[i].b + cistern[i].h );
49 checkmin( l, cistern[i].b );
50 }
51 scanf("%d",&volumn);
52 if(calc(r) < volumn){
53 printf("OVERFLOW\n");
54 continue;
55 }
56 printf("%.2lf\n", b_search(l , r) );
57 }
58 }
posted on 2009-11-02 22:26
wangzhihao 閱讀(179)
評論(0) 編輯 收藏 引用 所屬分類:
geometry