| ||||||||||
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 |
第一次半平面交happy#include<cstdio> #include<cstring> double Min(double a,double b){return a<b?a:b;} double Max(double a,double b){return a>b?a:b;} double Abs(double a){return a>0?a:-a;} struct Point {double x,y;}stk[1010],tstk[1010],pp[1010]; double mul(Point a,Point b,Point c) {return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);} double cross(Point a,Point b,Point c,Point d) {if(mul(a,c,b)*mul(a,d,b)<0)return true; return false; } Point crossp(Point a,Point b,Point c,Point d) {double a1,a2,b1,b2,c1,c2; Point cr; a1=b.y-a.y,b1=a.x-b.x,c1=b.x*a.y-a.x*b.y; a2=d.y-c.y,b2=c.x-d.x,c2=d.x*c.y-c.x*d.y; cr.x=(b1*c2-b2*c1)/(a1*b2-a2*b1); cr.y=(a1*c2-a2*c1)/(a2*b1-a1*b2); return cr; } int T,n,top; void calc(Point a,Point b) {double a1,b1,c1; a1=b.y-a.y,b1=a.x-b.x,c1=b.x*a.y-a.x*b.y; int ttop=0; for(int i=0;i<top;i++) {if(a1*stk[i].x+b1*stk[i].y+c1>=0)tstk[ttop++]=stk[i]; if(cross(a,b,stk[i],stk[i+1]))tstk[ttop++]=crossp(a,b,stk[i],stk[i+1]); }top=ttop; tstk[ttop]=tstk[0]; for(int i=0;i<=top;i++)stk[i]=tstk[i]; } int main() {scanf("%d",&T); while(T--) {scanf("%d",&n); for(int i=0;i<n;i++)scanf("%lf%lf",&pp[i].x,&pp[i].y); pp[n]=pp[0]; for(int i=0;i<=n;i++)stk[i]=pp[i]; top=n; for(int i=0;i<n;i++) calc(pp[i],pp[i+1]); if(top)puts("YES"); else puts("NO"); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator