UVA 634 Polygon(模板题:判定点在多边形内)

UVA 634 Polygon(模板题:判定点在多边形内)

题意:

给你一个n个顶点的多边形(所有点按时针顺序给出),然后再给你一个点p,问你这个点p是否在多边形内部?

分析:

直接用判定点是否在多边形内的模板即可. 模板参考刘汝佳书籍<<算法竞赛入门经典:训练指南>>P271.

模板最好是每个都自己手写,不要去直接复制粘贴哦,各种前辈的经验都说明反复的手写模板才是提高实力的正确方式.

AC代码:

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const double eps=1e-10;
const int maxn=1000+10;
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
struct Point
{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
};
typedef Point Vector;
Vector operator-(Point A,Point B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
double Dot(Vector A,Vector B)
{
    return A.x*B.x+A.y*B.y;
}
double Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
bool InSegment(Point P,Point A,Point B)
{
    return dcmp( Cross(A-B,P-B) )==0 && dcmp( Dot(A-P,B-P) )<=0;
}
bool PointInPolygon(Point p,Point*poly,int n)
{
    int wn=0;
    for(int i=0;i<n;++i)
    {
        if(InSegment(p,poly[i],poly[(i+1)%n])) return true;
        int k=dcmp( Cross(poly[(i+1)%n]-poly[i], p-poly[i] ) );
        int d1=dcmp( poly[i].y-p.y );
        int d2=dcmp( poly[(i+1)%n].y-p.y );
        if(k>0 && d1<=0 && d2>0) wn++;
        if(k<0 && d2<=0 && d1>0) wn--;
    }
    if(wn!=0) return true;
    return false;
}

int main()
{
    int n;
    while(scanf("%d",&n)==1 && n)
    {
        Point poly[maxn],p;
        for(int i=0;i<n;++i)
            scanf("%lf%lf",&poly[i].x,&poly[i].y);
        scanf("%lf%lf",&p.x,&p.y);
        printf("%c\n",PointInPolygon(p,poly,n)?'T':'F');
    }
    return 0;
}