hdu 1756 Cupid's Arrow 计算几何

    判断点是否在多边形内部

    对于任意四边形，可以随机选取一条射线向外延伸，如果相交边数为奇数，则在内，偶数，则在外

   这题无需考虑在边上的情况

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
给定n个点的坐标，这n个点依次围成一闭合多边形，再给一点（x，y），判断它是否在多边形中。
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define INF 1E9
#define eps 1e-8
using namespace std;
struct Node
{
    double x,y;
};
Node org[1000005];
Node A,B;
int n,i;
double cross(Node A, Node B, Node C)
{
    return (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x);
}
bool isZero(double x) {//判断x是否接近0
    return (x > 0 ? x : -x) < eps;
}
bool in()
{
    int count, i = 0;
    org[n] = org[0];
    while (i < n)
    {
        B.x = rand() + INF;  //随机取一个足够远的点B
        B.y = rand() + INF;  //以A为起点B为终点做射线L
        for (i=count=0; i<n; ++i)
        {
           /*
            if (isZero(cross(A,org[i],org[i+1]))&&
              (org[i].x-A.x)*(org[i+1].x-A.x)<eps&&(org[i].y-A.y)*(org[i+1].y-A.y)<eps)
                return 0;//点A在边上
           */
            if (isZero(cross(A, B, org[i]))) break;//点org[i]在射线AB上，停止本循环，另取B
            else if (cross(org[i], org[i+1], A)*cross(org[i], B, org[i+1])>eps &&//射线与边相交，统计交点数
                     cross(A, B, org[i])*cross(A, org[i+1], B)>eps)  ++count;
        }
    }
    return count & 1;
}

int main()
{
    while(~scanf("%d",&n))
    {
        for(i=0;i<n;i++)
        {
            scanf("%lf%lf",&org[i].x,&org[i].y);
        }
        int m;
        scanf("%d",&m);
        while(m--)
        {
            scanf("%lf%lf",&A.x,&A.y);
            if(in())puts("Yes");
            else puts("No");
        }
    }
}