| ||||||||||
| 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