HDU 1756 Cupid's Arrow(判断点是否在多边形内模板)

http://acm.hdu.edu.cn/showproblem.php?pid=1756

方法：求解以某点为起点的射线与多边形边的交点个数，奇数时则点在内，偶数在外

需要特别注意交点在顶峰和谷底以及射线与边平行的情况

#include<stdio.h>
#include<math.h>
typedef struct node
{
    double x,y;
}point;
point p,a[110],b;
int n;
double min(double a,double b)
{
    return a>b?b:a;
}
double max(double a,double b)
{
    return a>b?a:b;
}
int point_in_polygon(point p)
{
    int count=0,i;
    point p1,p2;
    double x;
    for(i=0;i<n;i++)
    {
        p1=a[i];
        p2=a[(i+1)%n];
        if(p1.y==p2.y)//p1p1与y=p.y平行,交点可由前一次，或后一次代为计算，否则可能会重复计算
            continue;
        if(p.y<min(p1.y,p2.y)||p.y>=max(p1.y,p2.y))//这里的这两种情况，都是关于交点在延长线上的，而前一个之所以没加入端点，因为前一次可能是平行，跳过了，所以要进行计算
            continue;
        x=-((p2.x*p1.y-p1.x*p2.y)+p.y*(p1.x-p2.x))/(p2.y-p1.y);//根据两点和交点y计算交点x
        count+=(x>p.x);//如果在点的右侧，则说明有交点
    }
    return count&1;
}
int main()
{
    int i,m;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%lf%lf",&a[i].x,&a[i].y);
        scanf("%d",&m);
        for(i=0;i<m;i++)
        {
            scanf("%lf%lf",&b.x,&b.y);
            printf("%s
",point_in_polygon(b)?"Yes":"No");
        }
    }
    return 0;
}