首页 > 代码库 > POJ 1584 A Round Peg in a Ground Hole 判断凸多边形 点到线段距离 点在多边形内

POJ 1584 A Round Peg in a Ground Hole 判断凸多边形 点到线段距离 点在多边形内

首先判断是不是凸多边形

然后判断圆是否在凸多边形内

kuangbin的板子,但是有些地方不明白。

判断多边形不是凸多边形后,为什么用判断点是否在凸多边形内的模板交WA了,而用判断点是否在任意多边形内的模板A了

而且判断点是否在任意多边形的注释,返回值为什么又说是凸多边形~~~

POJ 1584 A Round Peg in a Ground Hole(判断凸多边形,点到线段距离,点在多边形内)

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const double eps=1e-8;const double PI = acos(-1.0);int sgn(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;    }    Point operator -(const Point &b)const    {        return Point(x - b.x,y - b.y);    }    //叉积    double operator ^(const Point &b)const    {        return x*b.y - y*b.x;    }    //点积    double operator *(const Point &b)const    {        return x*b.x + y*b.y;    }    void input()    {        scanf("%lf%lf",&x,&y);    }};struct Line{    Point p,q;    Line() {};    Line(Point _p,Point _q)    {        p = _p,q = _q;    }};//*两点间距离double dist(Point a,Point b){    return sqrt((a-b)*(a-b));}//*判断凸多边形//允许共线边//点可以是顺时针给出也可以是逆时针给出//点的编号0~n-1bool isconvex(Point poly[],int n){    bool s[3];    memset(s,false,sizeof(s));    for(int i = 0; i < n; i++)    {        s[sgn( (poly[(i+1)%n]-poly[i])^(poly[(i+2)%n]-poly[i]) )+1] = true;        if(s[0] && s[2])return false;    }    return true;}//*点到线段的距离//返回点到线段最近的点Point NearestPointToLineSeg(Point P,Line L){    Point result;    double t = ((P-L.p)*(L.q-L.p))/((L.q-L.p)*(L.q-L.p));    if(t >= 0 && t <= 1)    {        result.x = L.p.x + (L.q.x - L.p.x)*t;        result.y = L.p.y + (L.q.y - L.p.y)*t;    }    else    {        result = dist(P,L.p) < dist(P,L.q)? L.p:L.q;    }    return result;}//*判断点在线段上bool OnSeg(Point P,Line L){    return        sgn((L.p-P)^(L.q-P)) == 0 &&        sgn((P.x - L.p.x) * (P.x - L.q.x)) <= 0 &&        sgn((P.y - L.p.y) * (P.y - L.q.y)) <= 0;}//*判断点在凸多边形内//点形成一个凸包,而且按逆时针排序(如果是顺时针把里面的<0改为>0)//点的编号:0~n-1//返回值://-1:点在凸多边形外//0:点在凸多边形边界上//1:点在凸多边形内int inConvexPoly(Point a,Point p[],int n){    for(int i = 0; i < n; i++)    {        if(sgn((p[i]-a)^(p[(i+1)%n]-a)) < 0)return -1;        else if(OnSeg(a,Line(p[i],p[(i+1)%n])))return 0;    }    return 1;}//*判断线段相交bool inter(Line l1,Line l2){    return        max(l1.p.x,l1.q.x) >= min(l2.p.x,l2.q.x) &&        max(l2.p.x,l2.q.x) >= min(l1.p.x,l1.q.x) &&        max(l1.p.y,l1.q.y) >= min(l2.p.y,l2.q.y) &&        max(l2.p.y,l2.q.y) >= min(l1.p.y,l1.q.y) &&        sgn((l2.p-l1.q)^(l1.p-l1.q))*sgn((l2.q-l1.q)^(l1.p-l1.q)) <= 0 &&        sgn((l1.p-l2.q)^(l2.p-l2.q))*sgn((l1.q-l2.q)^(l2.p-l2.q)) <= 0;}//*判断点在任意多边形内//射线法,poly[]的顶点数要大于等于3,点的编号0~n-1//返回值//-1:点在凸多边形外//0:点在凸多边形边界上//1:点在凸多边形内int inPoly(Point p,Point poly[],int n){    int cnt;    Line ray,side;    cnt = 0;    ray.p = p;    ray.q.y = p.y;    ray.q.x = -100000000000.0;//-INF,注意取值防止越界    for(int i = 0; i < n; i++)    {        side.p = poly[i];        side.q = poly[(i+1)%n];        if(OnSeg(p,side))return 0;        //如果平行轴则不考虑        if(sgn(side.p.y - side.q.y) == 0)            continue;        if(OnSeg(side.p,ray))        {            if(sgn(side.p.y - side.q.y) > 0)cnt++;        }        else if(OnSeg(side.q,ray))        {            if(sgn(side.q.y - side.p.y) > 0)cnt++;        }        else if(inter(ray,side)) cnt++;    }    return cnt % 2 ? 1:-1;}Point pot[105],peg;double rad;int main(){//    freopen("in.txt","r",stdin);    int n;    while(~scanf("%d",&n))    {        if(n<3) break;        scanf("%lf",&rad);        peg.input();        for(int i=0;i<n;i++)            pot[i].input();        if(!isconvex(pot,n))        {            puts("HOLE IS ILL-FORMED");            continue;        }        if(inPoly(peg,pot,n)<0)        {            puts("PEG WILL NOT FIT");            continue;        }        bool flag=true;        for(int i=0;i<n-1;i++)        {            if( sgn(dist(peg,NearestPointToLineSeg(peg,Line(pot[i],pot[(i+1)%n])))-rad)<0 )            {                flag=false;                break;            }        }        puts(flag? "PEG WILL FIT":"PEG WILL NOT FIT");    }    return 0;}

 

POJ 1584 A Round Peg in a Ground Hole 判断凸多边形 点到线段距离 点在多边形内