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 |
精度比较诡异,1e-1到1e-9都可以,0和1e-10就WA#include<iostream> #include<cmath> #include<algorithm> #define eps 1e-1 using namespace std; struct point { double x,y; }ps[120]; point origin={0.0,0.0}; double cross(point a,point b,point c) { return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x); } bool isinter(point a,point b,point c,point d) { return fabs((a.x-b.x)*(c.y-d.y)-(a.y-b.y)*(c.x-d.x))!=0.0; } point inter(point a,point b,point c,point d) { point res; double t1=cross(a,b,d),t2=cross(a,b,c); res.x=(t1*c.x-t2*d.x)/(t1-t2); res.y=(t1*c.y-t2*d.y)/(t1-t2); return res; } int n; bool isconter() { double res=0.0; ps[n]=ps[0]; int i; for(i=0;i<n;++i) res+=cross(ps[i],ps[i+1],origin); return res>0; } int main() { int cases; int i,j,k,s,t,r; point p; while(scanf("%d",&n),n) { for(i=0;i<n;++i) scanf("%lf%lf",&ps[i].x,&ps[i].y); if(!isconter()) reverse(ps,ps+n); ps[n]=ps[0]; for(i=0;i<n;++i) { for(j=i+1;j<n;++j) { if(isinter(ps[i],ps[i+1],ps[j],ps[j+1])) { p=inter(ps[i],ps[i+1],ps[j],ps[j+1]); for(k=0;k<n;++k) { if(cross(p,ps[k+1],ps[k])>eps)break; } if(k==n) break; } } if(j<n)break; } if(i>=n) printf("0"); else printf("1"); printf("\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