| ||||||||||
| 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 | |||||||||
哪位大神救救我呀 给点数据吧!一直wa呀 有木有#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=25;
//const double K=1e-10;
struct node
{
double x,y;
}uppoint[N];
struct node1
{
double x,y;
}downpoint[N];
void point_of_intersection(double px,double py,double x1,double y1,double qx,double qy,double x2,double y2,double *k1)
{
double K1=y1/x1;
double K2=y2/x2;
(*k1)=(qx*K2-qy+py-px*K1)/(K2-K1);
}
bool Can_keep_move(int l,int i,int j,double *k1)
{
double x1=downpoint[j].x-uppoint[i].x;
double y1=downpoint[j].y-uppoint[i].y;
double x2=downpoint[l].x-uppoint[i].x;
double y=(y1*x2)/x1+uppoint[i].y;
if(y<=uppoint[l].y&&y>=downpoint[l].y)
return true;
if(l<max(i,j))
return false;
x2=uppoint[l].x-uppoint[l-1].x;
double y2=uppoint[l].y-uppoint[l-1].y;
if(y>uppoint[l].y)
{
point_of_intersection(uppoint[i].x,uppoint[i].y,x1,y1,uppoint[l].x,uppoint[l].y,x2,y2,k1);
}
else
{
point_of_intersection(uppoint[i].x,uppoint[i].y,x1,y1,downpoint[l].x,downpoint[l].y,x2,y2,k1);
}
return false;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF,n)
{
for(int i=1;i<=n;++i)
{
scanf("%lf %lf",&uppoint[i].x,&uppoint[i].y);
downpoint[i].x=uppoint[i].x;
downpoint[i].y=uppoint[i].y-1;
}
bool through=false;
double ans=uppoint[1].x;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
if(i==j)
continue;
int l,r;
double lx,rx;
for(l=max(i,j)-1;l>0;--l)
{
if(!Can_keep_move(l,i,j,&lx))
break;
}
if(l!=0)
continue;
for(r=max(i,j)+1;r<=n;++r)
{
if(!Can_keep_move(r,i,j,&rx))
break;
}
if(r==n+1)
{
through=true;break;
}
else
{
if(rx>ans)
ans=rx;
}
}
if(through==true)
break;
}
if(through==false)
printf("%.2f\n",ans);
else
printf("Through all the pipe.\n");
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator