ZOJ 1081 Points Within 判断一个点是否在多边形内

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1081
Statement of the Problem

Several drawing applications allow us to draw polygons and almost all of them allow us to fill them with some color. The task of filling a polygon reduces to knowing which points are inside it, so programmers have to colour only those points.

You’re expected to write a program which tells us if a given point lies inside a given polygon described by the coordinates of its vertices. You can assume that if a point is in the border of the polygon, then it is in fact inside the polygon.

Input Format

The input file may contain several instances of the problem. Each instance consists of: (i) one line containing integers N, 0 < N < 100 and M, respectively the number of vertices of the polygon and the number of points to be tested. (ii) N lines, each containing a pair of integers describing the coordinates of the polygon’s vertices; (iii) M lines, each containing a pair of integer coordinates of the points which will be tested for “withinness” in the polygon.

You may assume that: the vertices are all distinct; consecutive vertices in the input are adjacent in the polygon; the last vertex is adjacent to the first one; and the resulting polygon is simple, that is, every vertex is incident with exactly two edges and two edges only intersect at their common endpoint. The last instance is followed by a line with a 0 (zero).

Output Format

For the ith instance in the input, you have to write one line in the output with the phrase “Problem i:”, followed by several lines, one for each point tested, in the order they appear in the input. Each of these lines should read “Within” or “Outside”, depending on the outcome of the test. The output of two consecutive instances should be separated by a blank line.

Sample Input

3 1
0 0
0 5
5 0
10 2
3 2
4 4
3 1
1 2
1 3
2 2
0

Sample Output

Problem 1:
Outside

Problem 2:
Outside
Within
题目大意：给出一个具有$n$n个点的多边形，对于每个询问$(x,y)$(x,y)，看该点是否在多边形内部。(包含边界)
思路：从该点做一条水平向右的射线，统计射线与多边形相交的情况，若相交次数为偶数，则说明该点在形外，否则在形内。为了便于交点在顶点或射线与某些边重合时的判断，可以将每条边看成左开右闭的线段，即若交点为左端点即不计算。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;

const double pi=acos(-1.0);//弧度pi
const double eps=1e-10;//精度

struct point
{
    double x,y;
    point(double a=0,double b=0)
    {
        x=a,y=b;
    }
    friend point operator * (point a,double b)
    {
        return point(a.x*b,a.y*b);
    }
    friend point operator * (double a,point b)
    {
        return point(b.x*a,b.y*a);
    }
    point operator - (const point &b)const
    {
        return point(x-b.x,y-b.y);
    }
    point operator + (const point &b)const
    {
        return point(x+b.x,y+b.y);
    }
    point operator / (const double b)const
    {
        return point(x/b,y/b);
    }
    bool operator < (const point &b)const//按坐标排序
    {
        if(fabs(x-b.x)<eps)
            return y<b.y-eps;
        return x<b.x-eps;
    }
    void transxy(double sinb,double cosb)//逆时针旋转b弧度
    {                                      //若顺时针 在传入的sinb前加个-即可
        double tx=x,ty=y;
        x=tx*cosb-ty*sinb;
        y=tx*sinb+ty*cosb;
    }
    void transxy(double b)//逆时针旋转b弧度
    {                     //若顺时针传入-b即可
        double tx=x,ty=y;
        x=tx*cos(b)-ty*sin(b);
        y=tx*sin(b)+ty*cos(b);
    }
    double norm()
    {
        return sqrt(x*x+y*y);
    }
};

inline double dot(point a,point b)//点积
{
    return a.x*b.x+a.y*b.y;
}
inline double cross(point a,point b)//叉积
{
    return a.x*b.y-a.y*b.x;
}

inline double dist(point a,point b)//两点间距离
{
    return (a-b).norm();
}

inline int sgn(double x)
{
    if(fabs(x)<eps)
        return 0;
    if(x>0)
        return 1;
    return -1;
}

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

bool point_on_seg(point p,point s,point t)//判断点p 是否在线段st上 包括端点
{
    return sgn(cross(p-s,t-s))==0&&sgn(dot(p-s,p-t))<=0;
}

typedef point Vector;

const int maxn=105;

struct polygon
{
    int n;//多边形顶点数
    point a[maxn];//0 到 n-1 顺时针顺序
    polygon() {}
    double perimeter()//计算多边形周长
    {
        double sum=0;
        a[n]=a[0];
        for(int i=0;i<n;i++)
            sum+=(a[i+1]-a[i]).norm();
        return sum;
    }
    double area()//计算多边形面积
    {
        double sum=0;
        a[n]=a[0];
        for(int i=0;i<n;i++)
            sum+=cross(a[i+1],a[i]);
        return sum/2;
    }
    int point_in(point t)//t在多边形外返回0 t在多边形内返回1 t在多边形边界上返回2
    {
        int num=0,d1,d2,k;
        a[n]=a[0];
        for(int i=0;i<n;i++)
        {
            if(point_on_seg(t,a[i],a[i+1]))
                return 2;
            k=sgn(cross(a[i+1]-a[i],t-a[i]));
            d1=sgn(a[i].y-t.y);
            d2=sgn(a[i+1].y-t.y);
            if(k>0&&d1<=0&&d2>0)
                ++num;
            if(k<0&&d2<=0&&d1>0)
                --num;
        }
        return num!=0;
    }
    point mass_center()//求多边形的重心坐标
    {
        point ans=point(0,0);
        if(sgn(area())==0)
            return ans;//多边形面积为0时重心没有定义 特判
        a[n]=a[0];
        for(int i=0;i<n;i++)
            ans=ans+(a[i]+a[i+1])*cross(a[i+1],a[i]);
        return ans/area()/6;
    }
    int border_int_point_num()
    {
        int num=0;
        a[n]=a[0];
        for(int i=0;i<n;i++)
            num+=gcd(abs(int(a[i+1].x-a[i].x)),abs(int(a[i+1].y-a[i].y)));
        return num;
    }
    int inside_int_point_num()
    {
        return int(area())+1-border_int_point_num()/2;
    }
};

int n,m;

int main()
{
    int times=0;
    while(~scanf("%d",&n)&&n)
    {
        if(times)
            printf("\n");
        scanf("%d",&m);
        polygon p;
        p.n=n;
        for(int i=0;i<n;i++)
            scanf("%lf%lf",&p.a[i].x,&p.a[i].y);
        double x,y;
        printf("Problem %d:\n",++times);
        while(m--)
        {
            scanf("%lf%lf",&x,&y);
            if(p.point_in(point(x,y))>=1)
                printf("Within\n");
            else
                printf("Outside\n");
        }
    }
    return 0;
}