判断点与多边形的位置关系

时间:2022-03-08 10:41:04

hdu1756

Cupid's Arrow

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1033    Accepted Submission(s): 382


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
程序:
#include"stdio.h"
#include"string.h"
#include"iostream"
#include"map"
#include"string"
#include"queue"
#include"stack"
#include"vector"
#include"stdlib.h"
#include"algorithm"
#include"math.h"
#define M 109
#define eps 1e-10
#define inf 0x3f3f3f3f
#define mod 1070000009
double const PI=acos(-1.0);
struct node
{
    double x,y;
}p[M];
struct line
{
    node s,e;
};
double max(double x,double y)
{
    return x>y?x:y;
}
double min(double x,double y)
{
    return x<y?x:y;
}
double cross(node a,node b,node c)
{
    double px1=b.x-a.x;
    double py1=b.y-a.y;
    double px2=c.x-a.x;
    double py2=c.y-a.y;
    return px1*py2-py1*px2;
}
int paichi(line a,line b)
{
    if(max(a.e.x,a.s.x)>min(b.s.x,b.e.x)
        &&max(b.e.x,b.s.x)>min(a.s.x,a.e.x)
        &&max(a.s.y,a.e.y)>min(b.s.y,b.e.y)
        &&max(b.s.y,b.e.y)>min(a.s.y,b.e.y))
        return 1;
    return 0;
}
int kuali(line a,line b)
{
    if(cross(a.s,a.e,b.s)*cross(a.s,a.e,b.e)<=0
        &&cross(b.s,b.e,a.s)*cross(b.s,b.e,a.e)<=0)
        return 1;
    return 0;
}
int judge(node q,int n)
{
    int flag;
    int i=0;
    while(i<=n)
    {
        node po;
        po.x=rand()+1000.0;
        po.y=rand()+1000.0;
        flag=0;
        for(i=1;i<=n;i++)
        {
            line a,b;
            a.s=q;
            a.e=po;
            b.s=p[i-1];
            b.e=p[i];
            if(q.x>=min(p[i-1].x,p[i].x)
               &&q.x<=max(p[i-1].x,p[i].x)
               &&q.y>=min(p[i-1].y,p[i].y)
               &&q.y<=max(p[i-1].y,p[i].y)&&fabs(cross(p[i-1],q,p[i]))<eps)
                return -1;//在边上
            else if(fabs(cross(po,q,p[i]))<eps)
                break;
            else if(kuali(a,b)&&paichi(a,b))
                flag++;
        }
    }
    return flag&1;//若是0在外面,否则在内部
}
int main()
{
    int n,i,m;
    while(scanf("%d",&n)!=-1)
    {
        for(i=1;i<=n;i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        p[0]=p[n];
        scanf("%d",&m);
        while(m--)
        {
            node g;
            scanf("%lf%lf",&g.x,&g.y);
            if(judge(g,n))
                printf("Yes\n");
            else
                printf("No\n");
        }
    }
    return 0;

}