首页 > 代码库 > poj1584 A Round Peg in a Ground Hole 判断多边形凹凸,点到线的距离【基础计算几何】

poj1584 A Round Peg in a Ground Hole 判断多边形凹凸,点到线的距离【基础计算几何】

大致思路:首先对于所给的洞的点,判断是否是凸多边形,图形的输入和输出可以是顺时针或者逆时针,而且允许多点共线

 

Debug 了好几个小时,发现如下问题

判断三点是否共线,可用斜率公式判断

POINT point_A, point_B, point_C;        if(point_A.x == point_B.x || point_B.x == point_C.x){            if(point_A.x == point_B.x && point_B.x == point_C.x)                continue;        }else{            if((point_B.y - point_A.y) / (point_B.x - point_A.x)                 == (point_C.y - point_B.y) / (point_C.x - point_B.x))                continue;        }

其次,判断圆是否和多边形相切的时候,应用:

if(Ptol(point, line2) - rr >= 0){

而不是:

 if(Ptol(point, line2) - rr >= eps){//eps = 1e-9

否则会出错。

 

贴代码了QAQ

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <cstring>#include <cmath>#include <stack>#include <queue>#include <vector>#include <algorithm>#define ll long long#define Max(a,b) (((a) > (b)) ? (a) : (b))#define Min(a,b) (((a) < (b)) ? (a) : (b))#define Abs(x) (((x) > 0) ? (x) : (-(x)))using namespace std;const int INF = 0x3f3f3f3f;const int MAXN = 220;const double eps = 1e-9;int gcd(int a,int b){    return b == 0 ? a : gcd(b, a % b);}struct POINT{    double x;    double y;    POINT() : x(0), y(0) {};    POINT(double _x_, double _y_) : x(_x_), y(_y_) {};};struct SEG{    POINT a;    POINT b;    SEG() {};    SEG(POINT _a_, POINT _b_) : a(_a_), b(_b_) {};};struct LINE{    POINT a;    POINT b;    LINE() {};    LINE(POINT _a_, POINT _b_) : a(_a_), b(_b_) {};};struct LINE2{    double A, B, C;    LINE2 () {};    LINE2(double _A_, double _B_, double _C_): A(_A_), B(_B_), C(_C_) {};};LINE2 Line2line(const LINE & L){    LINE2 L2;    L2.A = L.b.y - L.a.y;    L2.B = L.a.x - L.b.x;    L2.C = L.b.x * L.a.y - L.a.x * L.b.y;    return L2;}struct POLY{    int n;    double * x;    double * y;    POLY() : n(0), x(NULL), y(NULL) {};    POLY(int _n_, const double * _x_, const double * _y_){        n = _n_;        x = new double[n + 1];        memcpy(x, _x_, n * sizeof(double));        x[n] = _x_[0];        y = new double[n + 1];        memcpy(y, _y_, n * sizeof(double));        y[n] = _y_[0];    }};POINT vertex(const POLY & poly, int idx){    idx %= poly.n;    return POINT(poly.x[idx], poly.y[idx]);}SEG Edge(const POLY & poly, int idx){    idx %= poly.n;    return SEG(POINT(poly.x[idx], poly.y[idx]),        POINT(poly.x[idx + 1], poly.y[idx + 1]));}void Coefficient(const LINE & L, double & A, double & B, double & C){    A = L.b.y - L.a.y;    B = L.a.x - L.b.x;    C = L.b.x * L.a.y - L.a.x * L.b.y;}double Ptol(const POINT p, const LINE2 L){    return Abs(L.A * p.x + L.B * p.y + L.C) / sqrt(L.A * L.A + L.B * L.B);}bool IsEqual(double a, double b){    return (Abs(a - b) < eps);}bool IsEqual(const POINT & a, const POINT & b){    return (IsEqual(a.x, b.x) && IsEqual(a.y, b.y));}bool IsEqual(const LINE & A, const LINE & B){    double A1, B1, C1;    double A2, B2, C2;    Coefficient(A, A1, B1, C1);    Coefficient(B, A2, B2, C2);    return IsEqual(A1 * B2, A2 * B1) &&        IsEqual(A1 * C2, A2 * C1) &&        IsEqual(B1 * C2, B2 * C1);}double Cross(const POINT & a, const POINT & b, const POINT &o){    return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);}bool IsParallel(const LINE & A, const LINE & B){    double A1, B1, C1;    double A2, B2, C2;    Coefficient(A, A1, B1, C1);    Coefficient(B, A2, B2, C2);    /*    return (A1 * B2 == A2 * B1) &&        ((A1 * C2 != A2 * C1) || (B1 * C2 != B2 * C1));    */    return (A1 * B2 == A2 * B1);}bool IsIntersect(const LINE & A, const LINE & B){    return !IsParallel(A, B);}bool IsIntersect(const SEG & u, const SEG & v){    return (Cross(v.a, u.b, u.a) * Cross(u.b, v.b, u.a) >= 0) &&        (Cross(u.a, v.b, v.a) * Cross(v.b, u.b, v.a) >= 0) &&        (Max(u.a.x, u.b.x) >= Min(v.a.x, v.b.x)) &&        (Max(v.a.x, v.b.x) >= Min(u.a.x, u.b.x)) &&        (Max(u.a.y, u.b.y) >= Min(v.a.y, v.b.y)) &&        (Max(v.a.y, v.b.y) >= Min(u.a.y, u.b.y));}bool IsOnSeg(const SEG & seg, const POINT & p){    return (IsEqual(p, seg.a) || IsEqual(p, seg.b)) ||        (((p.x - seg.a.x) * (p.x - seg.b.x) < 0 ||        (p.y - seg.a.y) * (p.y - seg.b.y) < 0) &&        (IsEqual(Cross(seg.b, p, seg.a), 0)));}bool IsOnPoly(const POLY & poly, const POINT & p){    for(int i = 0; i < poly.n; ++i){        if(IsOnSeg(Edge(poly, i), p)){            return true;        }    }    return false;}bool IsInPoly(const POLY & poly, const POINT & p){    SEG L(p, POINT(INF, p.y));    int count = 0;    for(int i = 0; i < poly.n; ++i){        SEG S = Edge(poly, i);        if(IsOnSeg(S, p)){            return true;        }        if(!IsEqual(S.a.y, S.b.y)){            POINT & q = (S.a.y > S.b.y) ? (S.a) : (S.b);            if(IsOnSeg(L, q)){                ++count;            } else if(!IsOnSeg(L, S.a) && !IsOnSeg(L, S.b) && IsIntersect(S, L)){                ++count;            }        }    }    return (count % 2 != 0);}POINT InCenter(const POLY & poly){    double S, Si, Ax, Ay;    POINT p;    Si = (poly.x[poly.n - 1] * poly.y[0] - poly.x[0] * poly.y[poly.n - 1]);    S = Si;    Ax = Si * (poly.x[0] + poly.x[poly.n - 1]);    Ay = Si * (poly.y[0] + poly.y[poly.n - 1]);    for(int i = 1; i < poly.n; ++i){        Si = (poly.x[i - 1] * poly.y[i] - poly.x[i] * poly.y[i - 1]);        Ax += Si * (poly.x[i - 1] + poly.x[i]);        Ay += Si * (poly.y[i - 1] + poly.y[i]);        S += Si;    }    S = S * 3;    return POINT(Ax/S, Ay/S);}double Area(const POLY & poly){    if(poly.n < 3)  return double(0);    double s = poly.y[0] * (poly.x[poly.n - 1] - poly.x[1]);    for(int i = 1; i < poly.n; ++i){        s += poly.y[i] * (poly.x[i - 1] - poly.x[(i + 1) % poly.n]);    }    return s / 2;}int PointInedge(const POLY & poly){    int ans = 0;    for(int i = 0; i < poly.n; ++i){        double xx = Abs(poly.x[i] - poly.x[i + 1]);        double yy = Abs(poly.y[i] - poly.y[i + 1]);        if(xx == 0 && yy == 0)            ans += 0;        else if(xx == 0)            ans += yy - 1;        else if(yy == 0)            ans += xx- 1 ;        else            ans += gcd(xx, yy) - 1;    }    return ans + poly.n;}bool IsConvexPolygon(const POLY & poly){    double ans ,cnt = 1.0;    bool flag ,real = false;    for(int i = 0; i < poly.n; ++i){        ans = (poly.x[i] - poly.x[(i + 2) % poly.n])            * (poly.y[(i + 1) % poly.n] - poly.y[(i + 2) % poly.n])            - (poly.x[(i + 1) % poly.n] - poly.x[(i + 2) % poly.n])            * (poly.y[i] - poly.y[(i + 2) % poly.n]);        POINT point_A, point_B, point_C;        if(point_A.x == point_B.x || point_B.x == point_C.x){            if(point_A.x == point_B.x && point_B.x == point_C.x)                continue;        }else{            if((point_B.y - point_A.y) / (point_B.x - point_A.x)                 == (point_C.y - point_B.y) / (point_C.x - point_B.x))                continue;        }        if(real && cnt * ans < eps) return false;        cnt = ans;        real = true;    }    return true;}double x[20011], y[20011];int main(){    int i, j, k;    int t, n, m;    double rr, xx, yy;    while(EOF != scanf("%d",&n)){        if(n < 3)   break;        POINT point;        scanf("%lf%lf%lf",&rr,&point.x,&point.y);        for(i = 0; i < n; ++i)            scanf("%lf%lf",&x[i],&y[i]);        POLY poly(n, x, y);        if(!IsConvexPolygon(poly))            printf("HOLE IS ILL-FORMED\n");        else{            if(!IsInPoly(poly, point)){                printf("PEG WILL NOT FIT\n");            }            else{                for(i = 0; i < n; ++i){                    SEG seg = Edge(poly, i);                    LINE line;                    LINE2 line2;                    line.a = seg.a;                    line.b = seg.b;                    line2 = Line2line(line);                    if(Ptol(point, line2) - rr >= 0){                        continue;                    }                    else{                        printf("PEG WILL NOT FIT\n");                        break;                    }                }                if(i == n){                    printf("PEG WILL FIT\n");                }            }        }    }    return 0;}