学步园

判断点在一个凸多边形里面

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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>

using namespace std;

const int maxn=110;
const double eps=1e-8;
const double pi=acos(-1.0);

inline double sqr(double x)
{
    return x*x;
}

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

struct point
{
    double x,y;
    point(){};
    point(double a,double b):x(a),y(b){}
    void input()
    {
        scanf("%lf%lf",&x,&y);
    }
    friend point operator + (const point &a,const point &b)
    {
        return point(a.x+b.x,a.y+b.y);
    }
    friend point operator - (const point &a,const point &b)
    {
        return point(a.x-b.x,a.y-b.y);
    }
    friend bool operator == (const point &a,const point &b)
    {
        return sig(a.x-b.x)==0 && sig(a.y-b.y)==0;
    }
    friend point operator * (const point &a,const double &b)
    {
        return point(a.x*b,a.y*b);
    }
    friend point operator * (const double &a,const point &b)
    {
        return point(a*b.x,a*b.y);
    }
    friend point operator / (const point &a,const double &b)
    {
        return point(a.x/b,a.y/b);
    }
    double norm()
    {
        return sqrt(sqr(x)+sqr(y));
    }
};

double det(const point &a,const point &b)
{
    return a.x*b.y-a.y*b.x;
}

double dot(const point &a,const point &b)
{
    return a.x*b.x+a.y*b.y;
}

double dist(const point &a,const point &b)
{
    return (a-b).norm();
}

bool PointOnSegment(point p,point s,point t)
{
    return sig(det(p-s,t-s))==0 && sig(dot(p-s,p-t))<=0;
}


struct polygon
{
    int n;
    point a[maxn];
    polygon(){}
    int judDir()
    {
        int d;
        a[n]=a[0];
        for(int i=0;i<n-1;i++)
        {
            d=sig(det(a[i+1]-a[i],a[i+2]-a[i+1]));
            if(d!=0) break;
        }
        return d;
    }
    void to_counter_clockwise()
    {
        for(int i=0;i<(n)/2;i++)  swap(a[i],a[n-1-i]);
    }
    int Point_In(point t)
    {
        int num=0,d1,d2,k;
        a[n]=a[0];
        for(int i=0;i<n;i++)
        {
            if(PointOnSegment(t,a[i],a[i+1])) return 2;
            k=sig(det(a[i+1]-a[i],t-a[i]));
            d1=sig(a[i].y-t.y);
            d2=sig(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;
    }
};

polygon  pl;
point p;
int n;
int main()
{
    int cs=1;
    while(cin>>n)
    {
        if(n==0) break;
        if(cs!=1) printf("\n");

        int m;
        cin>>m;
        pl.n=n;
        for(int i=0;i<n;i++)
            pl.a[i].input();
        if(pl.judDir()==1) pl.to_counter_clockwise();
        printf("Problem %d:\n",cs++);
        for(int i=0;i<m;i++)
        {
            p.input();
            if(pl.Point_In(p))
            {
                printf("Within\n");
            }
            else
            {
                printf("Outside\n");
            }
        }

    }
    return 0;
}