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