| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
从下往上扫~~飘过~~~4700MS++~~嘿嘿#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<map>
#include<cstdlib>
#include<cmath>
#include<vector>
#define LL long long
#define IT __int64
#define zero(x) fabs(x)<eps
#define mm(a,b) memset(a,b,sizeof(a))
const int INF=0x7fffffff;
const double inf=1e8;
const double eps=1e-10;
const double PI=acos(-1.0);
const int Max=50001;
using namespace std;
int sign(double x)
{
return (x>eps)-(x<-eps);
}
struct Cisterns
{
int b;
int h;
int w;
int d;
int sum;
Cisterns(const int &_b=0,const int &_h=0,const int &_w=0,const int &_d=0,const int &_sum=0):b(_b),h(_h),w(_w),d(_d),sum(_sum){}
void input()
{
cin>>b>>h>>w>>d;
}
void output()
{
cout<<b<<" "<<h<<" "<<w<<" "<<d<<endl;
}
}cs[Max];
struct Node
{
int h;
int f;
}node[Max];
bool cmp(Node u,Node v)
{
return u.h<v.h;
}
int s[Max];
int main()
{
int k,n,m,i,j;
int res;
double Total_V;
double Total_H;
int sum;
cin>>k;
while(k--)
{
cin>>n;
res=0;
m=0;
for(i=1;i<=n;i++)
{
cs[i].input();
cs[i].sum=cs[i].h*cs[i].w*cs[i].d;
s[i]=cs[i].w*cs[i].d;
node[m].h=cs[i].b;
node[m++].f=i;
node[m].h=cs[i].b+cs[i].h;
node[m++].f=-i;
res+=cs[i].sum;
}
cin>>Total_V;
if(Total_V>res)
cout<<"OVERFLOW"<<endl;
else
{
sort(node,node+m,cmp);
Total_H=node[0].h;
sum=0;
for(i=0;i<m;i++)
{
if(i>0&&node[i].h>node[i-1].h)
{
Total_V-=sum*(node[i].h-node[i-1].h);
//cout<<Total_V<<endl;
Total_H+=node[i].h-node[i-1].h;
if(Total_V<=0)
{
Total_H+=Total_V/sum;
break;
}
}
if(node[i].f<0)
sum-=s[-node[i].f];
else
sum+=s[node[i].f];
//cout<<sum<<endl;
}
cout<<setprecision(2)<<setiosflags(ios::fixed)<<Total_H<<endl;
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator