hdu 1756 Cupid's Arrow(计算几何)

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 #define MAXN 1007
 4 #define offset 10000
 5 #define eps 1e-10
 6 //浮点数判 0
 7 #define zero(x) (((x)>0?(x):-(x))<eps)
 8 //浮点数判断符
 9 #define _sign(x) ((x)>eps?1:((x)<-eps?2:0))
10 //定义点
11 struct point
12 {
13     double x,y;
14 }pt[MAXN],tmp;
15 double xmult(point p1,point p2,point p0)
16 {
17     return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
18 }
19 int inside_polygon(point q,int n,point* p,int on_edge=2)
20 {
21     point q2;
22     int i=0,count;
23     while (i<n)
24     for (count=i=0,q2.x=rand()+offset,q2.y=rand()+offset;i<n;i++)
25     {
26         if (zero(xmult(q,p[i],p[(i+1)%n]))&&(p[i].x-q.x)*(p[(i+1)%n].x-q.x)<eps&&(p[i].y-q.y)*(p[(i+1)%n].y-q.y)<eps)
27             return on_edge;
28         else if (zero(xmult(q,q2,p[i])))break;
29         else if (xmult(q,p[i],q2)*xmult(q,p[(i+1)%n],q2)<-eps&&
30         xmult(p[i],q,p[(i+1)%n])*xmult(p[i],q2,p[(i+1)%n])<-eps)
31         count++;
32     }
33     return count&1;
34 }
35 int n,m;
36 int main()
37 {
38     while(~scanf("%d",&n))
39     {
40         F(i,0,n-1)scanf("%lf%lf",&pt[i].x,&pt[i].y);
41         scanf("%d",&m);
42         F(i,1,m)
43         {
44             scanf("%lf%lf",&tmp.x,&tmp.y);
45             puts(inside_polygon(tmp,n,pt)?"Yes":"No");
46         }
47     }
48     return 0;
49 }