Cupid's Arrow

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 849    Accepted Submission(s): 306

Problem Description

传说世上有一支丘比特的箭，凡是被这支箭射到的人，就会深深的爱上射箭的人。

世上无数人都曾经梦想得到这支箭。Lele当然也不例外。不过他想，在得到这支箭前，他总得先学会射箭。

日子一天天地过，Lele的箭术也越来越强，渐渐得，他不再满足于去射那圆形的靶子，他开始设计各种各样多边形的靶子。

不过，这样又出现了新的问题，由于长时间地练习射箭，Lele的视力已经高度近视，他现在甚至无法判断他的箭射到了靶子没有。所以他现在只能求助于聪明的Acmers，你能帮帮他嘛？

 

 

Input

本题目包含多组测试，请处理到文件结束。

在每组测试的第一行，包含一个正整数N(2<N<100),表示靶子的顶点数。

接着N行按顺时针方向给出这N个顶点的x和y坐标(0<x,y<1000)。

然后有一个正整数M，表示Lele射的箭的数目。

接下来M行分别给出Lele射的这些箭的X,Y坐标(0<X,Y<1000)。

 

 

Output

对于每枝箭，如果Lele射中了靶子，就在一行里面输出"Yes",否则输出"No"。

 

 

Sample Input

4

10 10

20 10

20 5

10 5

2

15 8

25 8

 

 

Sample Output

Yes

No

 

 

Author

linle

 

 

Source

 

 

Recommend

lcy   |   We have carefully selected several similar problems for you:            

---

 

　　计算几何：判断点在多边形内。

　　开始看这类题算法感觉不难，就是需要考虑的很多，结果自己写模板的时候才发现真心麻烦。WA了好多次，发现是自己想漏了。最后一次提交的时候心情还是很忐忑，不过总算AC了。

　　下面是这类题算法的思路，我就是照着下面链接的思路写的模板，具体我就不写在这里了，链接里介绍的很详细：

　　

　　我的模板（未优化）：

1 //判断点q是否在多边形内 2 //任意凸或者凹多边形 3 //顶点集合p[]按逆时针或者顺时针顺序存储(1..pointnum) 4 struct Point{ 5     double x,y; 6 }; 7 struct Line{ 8     Point p1,p2; 9 };10 double xmulti(Point p1,Point p2,Point p0)    //求p1p0和p2p0的叉积,如果大于0,则p1在p2的顺时针方向11 {12     return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);13 }14 double Max(double a,double b)15 {16     return a>b?a:b;17 }18 double Min(double a,double b)19 {20     return a
      
        Max(l.p1.x,l.p2.x) || q.x < Min(l.p1.x,l.p2.x)25         || q.y > Max(l.p1.y,l.p2.y) || q.y < Min(l.p1.y,l.p2.y) )26         return false;27     if(xmulti(l.p1,l.p2,q)==0)    //点q不在l的延长线或者反向延长线上，如果叉积再为0，则确定点q在线段l上28         return true;29     else30         return false;31 }32 bool pinplg(int pointnum,Point p[],Point q)33 {34     Line s;35     int c = 0;36     for(int i=1;i<=pointnum;i++){    //多边形的每条边s37         if(i==pointnum)38             s.p1 = p[pointnum],s.p2 = p[1];39         else40             s.p1 = p[i],s.p2 = p[i+1];41         if(ponls(q,s))    //点q在边s上42             return true;43         if(s.p1.y != s.p2.y){    //s不是水平的44             Point t;45             t.x = q.x - 1,t.y = q.y;46             if( (s.p1.y == q.y && s.p1.x <=q.x) || (s.p2.y == q.y && s.p2.x <= q.x) ){    //s的一个端点在L上47                 int tt;48                 if(s.p1.y == q.y)49                     tt = 1;50                 else if(s.p2.y == q.y)51                     tt = 2;52                 int maxx;53                 if(s.p1.y > s.p2.y)54                     maxx = 1;55                 else56                     maxx = 2;57                 if(tt == maxx) //如果这个端点的纵坐标较大的那个端点58                     c++;59             }60             else if(xmulti(s.p1,t,q)*xmulti(s.p2,t,q) <= 0){    //L和边s相交61                 Point lowp,higp;62                 if(s.p1.y > s.p2.y)63                     lowp.x = s.p2.x,lowp.y = s.p2.y,higp.x = s.p1.x,higp.y = s.p1.y;64                 else65                     lowp.x = s.p1.x,lowp.y = s.p1.y,higp.x = s.p2.x,higp.y = s.p2.y;66                 if(xmulti(q,higp,lowp)>=0)67                     c++;68             }69         }70     }71     if(c%2==0)72         return false;73     else74         return true;75 }
      

 

　　吉林大学的模板，很精练：

1 /*=============================================== 2 | 判断点q是否在多边形内 3 其中多边形是任意的凸或凹多边形， 4 Polygon中存放多边形的逆时针顶点序列 5 ================================================*/ 6 int pinplg(int vcount,Lpoint Polygon[],Lpoint q) 7 { 8 int c=0,i,n; 9 Llineseg l1,l2;10 l1.a=q; l1.b=q; l1.b.x=infinity; n=vcount;11 for (i=0;i
      
       0)21 ||22 (ponls(l1,Polygon[(i+2)%n]))&&23 (xmulti(Polygon[i],Polygon[(i+2)%n],l1.a) *24 xmulti(Polygon[(i+2)%n],Polygon[(i+3)%n],l1.a)>0)25 ) ) ) c++;26 }27 return(c%2!=0);28 }
      

 

　　题目代码：

1 #include 
      
        2 using namespace std; 3 //判断点q是否在多边形内 4 //任意凸或者凹多边形 5 //顶点集合p[]按逆时针或者顺时针顺序存储(1..pointnum) 6 struct Point{ 7     double x,y; 8 }; 9 struct Line{10     Point p1,p2;11 };12 double xmulti(Point p1,Point p2,Point p0)    //求p1p0和p2p0的叉积,如果大于0,则p1在p2的顺时针方向13 {14     return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);15 }16 double Max(double a,double b)17 {18     return a>b?a:b;19 }20 double Min(double a,double b)21 {22     return a
       
         Max(l.p1.x,l.p2.x) || q.x < Min(l.p1.x,l.p2.x)27         || q.y > Max(l.p1.y,l.p2.y) || q.y < Min(l.p1.y,l.p2.y) )28         return false;29     if(xmulti(l.p1,l.p2,q)==0)    //点q不在l的延长线或者反向延长线上，如果叉积再为0，则确定点q在线段l上30         return true;31     else32         return false;33 }34 bool pinplg(int pointnum,Point p[],Point q)35 {36     Line s;37     int c = 0;38     for(int i=1;i<=pointnum;i++){    //多边形的每条边s39         if(i==pointnum)40             s.p1 = p[pointnum],s.p2 = p[1];41         else42             s.p1 = p[i],s.p2 = p[i+1];43         if(ponls(q,s))    //点q在边s上44             return true;45         if(s.p1.y != s.p2.y){    //s不是水平的46             Point t;47             t.x = q.x - 1,t.y = q.y;48             if( (s.p1.y == q.y && s.p1.x <=q.x) || (s.p2.y == q.y && s.p2.x <= q.x) ){    //s的一个端点在L上49                 int tt;50                 if(s.p1.y == q.y)51                     tt = 1;52                 else if(s.p2.y == q.y)53                     tt = 2;54                 int maxx;55                 if(s.p1.y > s.p2.y)56                     maxx = 1;57                 else58                     maxx = 2;59                 if(tt == maxx) //如果这个端点的纵坐标较大的那个端点60                     c++;61             }62             else if(xmulti(s.p1,t,q)*xmulti(s.p2,t,q) <= 0){    //L和边s相交63                 Point lowp,higp;64                 if(s.p1.y > s.p2.y)65                     lowp.x = s.p2.x,lowp.y = s.p2.y,higp.x = s.p1.x,higp.y = s.p1.y;66                 else67                     lowp.x = s.p1.x,lowp.y = s.p1.y,higp.x = s.p2.x,higp.y = s.p2.y;68                 if(xmulti(q,higp,lowp)>=0)69                     c++;70             }71         }72     }73     if(c%2==0)74         return false;75     else76         return true;77 }78 int main()79 {80     int N,M;81     Point p[105];82     while(cin>>N){83         for(int i=1;i<=N;i++)84             cin>>p[i].x>>p[i].y;85         cin>>M;86         while(M--){87             Point q;88             cin>>q.x>>q.y;89             if(pinplg(N,p,q))90                 cout<<"Yes"<
       
      

 

Freecode :