地址：http://poj.org/problem?id=1434
| Time Limit: 5000MS | Memory Limit: 10000K | |
| Total Submissions: 4131 | Accepted: 1360 |
Description
You have been asked to write a program to compute the level to which cisterns will be lled with a certain volume of water, given the dimensions and position of each cistern. To simplify we will neglect the volume of water in the pipes.
Task
Write a program which for each data set:
reads the description of cisterns and the volume of water,
computes the level to which the cisterns will be filled with the given amount of water,
writes the result.
Input
The first line of each data set contains one integer n, the number of cisterns, 1 <= n <= 50 000. Each of the following n lines consists of 4 nonnegative integers, separated by single spaces: b, h, w, d - the base level of the cistern, its height, width and depth in meters, respectively. The integers satisfy 0 <= b <= 10^6 and 1 <= h * w * d <= 40 000. The last line of the data set contains an integer V - the volume of water in cubic meters to be injected into the network. Integer V satisfies 1 <= V <= 2 * 10^9.
Output
Line i, 1 <= i <= d, should contain the level that the water will reach, in meters, rounded up to two fractional digits, or the word 'OVERFLOW', if the volume of water exceeds the total capacity of the cisterns.
Sample Input
3
2
0 1 1 1
2 1 1 1
1
4
11 7 5 1
15 6 2 2
5 8 5 1
19 4 8 1
132
4
11 7 5 1
15 6 2 2
5 8 5 1
19 4 8 1
78
Sample Output
1.00
OVERFLOW
17.00
Source
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath> using namespace std; #define MP make_pair
#define PB push_back
#define lc (o<<1)
#define rc (o<<1|1)
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-;
const double pi=acos(-1.0);
const int K=5e4+;
const int mod=1e9+; struct node
{
double b,h,s;
bool operator < (const node &ta) const
{
return b<ta.b;
}
}cis[K];
int n;
double v;
int sgn(double ta,double tb)
{
if(fabs(ta-tb)<eps) return ;
return ta<tb?-:;
}
bool check(double x)
{
double ret=;
for(int i=;i<=n;i++)
{
if(sgn(cis[i].b,x)>) break;
ret+=cis[i].s*min(cis[i].h,x-cis[i].b);
}
return sgn(ret,v)>=;
}
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
double sum=,l=1e9,r=-1e9;
for(int i=;i<=n;i++)
{
double b,h,w,d;
scanf("%lf%lf%lf%lf",&b,&h,&w,&d);
cis[i]=(node){b,h,w*d};
sum+=h*w*d;
l=min(l,b),r=max(r,b+h);
}
sort(cis+,cis++n);
scanf("%lf",&v);
if(sgn(v,sum)>)
{
printf("OVERFLOW\n");
continue;
}
while(r-l>0.001)
{
double mid=(l+r)/;
if(check(mid))
r=mid;
else
l=mid;
}
printf("%.2f\n",l);
}
return ;
}