首页 > ACM题库 > HDU-杭电 > HDU 3918-Beiju[解题报告]HOJ
2015
04-14

HDU 3918-Beiju[解题报告]HOJ

Beiju

问题描述 :

Tclsm is a beiju guy, so is the beiju he has just bought. The shape he bought beiju (or cup) is not a regular cylinder, but a container with zigzag wall, as the figure shows. Tclsm wanted to know how much water the beiju can hold. As a sophisticated programmer, you are asked to help him.
Placing the beiju on the floor without constraint and pour water into it slowly, the moment water streams out from the beiju, or the beiju falls down,the volume of the water reaches the maximum.
To simplify the problem, you can assume the beiju in 2-dimensional case. There are two walls of the beiju �C the left one and the right one. The bottom of the beiju is entirely on the floor.
Road constructions

输入:

The first line of the input is T, the number of test cases.
Each case has thee lines.
First line has two integers �C m n, 1 < m, n < 100. the number of break point of the left wall and the right wall.
Second line has 2m integers, p0x p0y p1x p1y……pm-1x pm-1y, describing the coordinate of the break points in the left wall, from the bottom to top.
Third line has 2n integers, q0x q0y q1x q1y……qn-1x qn-1y, describing the coordinate of the break points in the right wall, from the bottom to top.
You can assume:
  • p0y < p1y <……< pm-1y,q0y < q1y <……< qm-1y,p0y = q0y, p0x < q0x
  • The two walls do not touch or intersect.
  • The two walls have zero thickness.
  • All the numbers in the input are in the range [0, 1000].

输出:

The first line of the input is T, the number of test cases.
Each case has thee lines.
First line has two integers �C m n, 1 < m, n < 100. the number of break point of the left wall and the right wall.
Second line has 2m integers, p0x p0y p1x p1y……pm-1x pm-1y, describing the coordinate of the break points in the left wall, from the bottom to top.
Third line has 2n integers, q0x q0y q1x q1y……qn-1x qn-1y, describing the coordinate of the break points in the right wall, from the bottom to top.
You can assume:
  • p0y < p1y <……< pm-1y,q0y < q1y <……< qm-1y,p0y = q0y, p0x < q0x
  • The two walls do not touch or intersect.
  • The two walls have zero thickness.
  • All the numbers in the input are in the range [0, 1000].

样例输入:

2
3 3
0 0 1 1 2 2
1 0 2 1 3 2
2 2
0 0 0 2
1 0 1 2

样例输出:

1.000
2.000

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const double O=1e-6;
struct point{ double x,y;
 point(double x0=0,double y0=0){ x=x0; y=y0;}
 point operator +(point b){ return point(x+b.x,y+b.y);}
 point operator *(double k){ return point(k*x,k*y);}
 point operator -(point b){ return point(b.x-x,b.y-y);}
 double operator %(point b){ return x*b.y-y*b.x;}
}p[3000];
double s,wx,wy,y[3000];
int n,m;

void put(point o,point a,point b){
 s+=(o-a)%(o-b);
 wx+=(o-a)%(o-b)*(o.x+a.x+b.x)/3;
 wy+=(o-a)%(o-b)*(o.y+a.y+b.y)/3;
}

int check(double y){
 point lp,rp;
 s=0; wx=0; wy=0;
 for (int j=1;j<=n;j++){
 if ( p[j+1].y>y+O ){
 lp=p[j]+(p[j]-p[j+1])*((y-p[j].y)/(p[j+1].y-p[j].y));
 put(p[1],p[j],lp);
 break;
 }
 put(p[1],p[j],p[j+1]);
 }
 for (int j=n+1;j<=n+m;j++){
 if ( p[j+1].y>y+O ){
 rp=p[j]+(p[j]-p[j+1])*((y-p[j].y)/(p[j+1].y-p[j].y));
 put(p[1],rp,p[j]);
 break;
 }
 put(p[1],p[j+1],p[j]);
 }
 put(p[1],lp,rp);
 double mx=wx/s;
 if ( mx<p[1].x-O || mx>p[n+1].x+O )
 return false;
 else return true;
}

int main(){
int test;
scanf("%d",&test);
while ( test-- ){
 scanf("%d%d",&n,&m);
 for (int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
 for (int i=1;i<=m;i++) scanf("%lf%lf",&p[i+n].x,&p[i+n].y);
 for (int i=1;i<=n+m;i++) p[i].y-=p[1].y;
 for (int i=1;i<=n+m;i++) y[i]=p[i].y;
 sort(y+1,y+n+m+1);
 int k=n+m;
 for (int i=1;i<=n+m;i++){
 if ( !check(y[i]) || y[i+1]>p[n].y+O || y[i+1]>p[n+m].y+O ){
 k=i;
 break;
 }
 }
 double l=y[k-1],r=y[k];
// printf("%d\n",k);
 while ( l+O<r ){
 double mid=(l+r)/2;
 if ( check(mid) )
 l=mid;
 else r=mid;
 }
 printf("%.3lf\n",l);
}
}

  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.