随笔-21  评论-10  文章-21  trackbacks-0
二分,单独判溢出的情况

 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 阅读(144) 评论(0)  编辑 收藏 引用 所属分类: geometry

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理