首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。