Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

第一次半平面交happy

Posted by testid1 at 2014-01-19 01:57:52 on Problem 3335
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator