| ||||||||||
| 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 | |||||||||
提交快100次了 还是wa 到底是不是精度问题啊 求大侠教 附代码 g++#include <iostream>
#include <fstream>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int Max=25;
struct Point
{
double x,y1,y2;
bool operator<(const Point &a)const
{
return x<a.x;
}
}point[Max];
int n;
int zero(double x)
{
if (x<-0.000000001)return -1;
if (x>0.000000001)return 1;
return 0;
}
double chacheng(double x,double y,double i,double j)
{
return x*j-y*i;
}
double fab(double x)
{
if (zero(x)==-1)return -x;
if (zero(x)==0)return 0;
return x;
}
double jiaodian(double x,double y,int k,int flag,int i)
{
double s1,s2,x1,y1,x2,y2;
x1=point[i-1].x-point[k].x;
x2=point[i].x-point[k].x;
if (flag==1)
{
y1=point[i-1].y1-point[k].y1;
y2=point[i].y1-point[k].y1;
}
else
{
y1=point[i-1].y1-point[k].y2;
y2=point[i].y1-point[k].y2;
}
s1=chacheng(x,y,x1,y1);
s2=chacheng(x,y,x2,y2);
if (zero(s1*s2)>=0)
{
if (flag==1)
{
y1=point[i-1].y2-point[k].y1;
y2=point[i].y2-point[k].y1;
}
else
{
y1=point[i-1].y2-point[k].y2;
y2=point[i].y2-point[k].y2;
}
s1=chacheng(x,y,x1,y1);
s2=chacheng(x,y,x2,y2);
}
if(zero(s1*s2)>=0)return point[i-1].x;
s1=fab(s1);
s2=fab(s2);
// cout<<s1<<" "<<s2<<" "<<point[i-1].x<<" "<<point[i].x<<endl;
return (s2*point[i-1].x+s1*point[i].x)/(s1+s2);
}
double test(double x,double y,int k,int flag)
{
int i,x0,y1,y2;
for (i=0;i<k;++i)
{
x0=point[k].x-point[i].x;
if (flag==1)
{
y1=point[k].y1-point[i].y1;
y2=point[k].y1-point[i].y2;
}
else
{
y1=point[k].y2-point[i].y1;
y2=point[k].y2-point[i].y2;
}
if (zero(chacheng(x,y,x0,y1)*chacheng(x,y,x0,y2))<=0)
{
continue;
}
return point[0].x;
}
for (i=k+1;i<n;++i)
{
x0=point[k].x-point[i].x;
if (flag==1)
{
y1=point[k].y1-point[i].y1;
y2=point[k].y1-point[i].y2;
}
else
{
y1=point[k].y2-point[i].y1;
y2=point[k].y2-point[i].y2;
}
if (zero(chacheng(x,y,x0,y1)*chacheng(x,y,x0,y2))<=0)
{
continue;
}
return jiaodian(x,y,k,flag,i);
}
return point[n-1].x;
}
int main()
{
// freopen("in.txt","r",stdin);
int i,j;
while (scanf("%d",&n)!=EOF)
{
if (n==0)break;
for (i=0;i<n;++i)
{
scanf("%lf%lf",&point[i].x,&point[i].y1);
point[i].y2=point[i].y1-1;
}
sort(point,point+n);
double x,y,temp0,ans=point[0].x;
for (i=0;i<n;++i)
{
for (j=0;j<n;++j)
{
if(i==j)continue;
x=point[i].x-point[j].x;
y=point[i].y1-point[j].y2;
if (i<j)
{
temp0=test(x,y,j,2);
}
else
{
temp0=test(x,y,i,1);
}
// cout<<temp0<<endl;
if (temp0>ans)ans=temp0;
}
}
if (ans>=point[n-1].x)printf("Through all the pipe.\n");
else printf("%.2f\n",ans);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator