【计算几何初步】POJ1584[A Round Peg in a Ground Hole]题解

题目概述

给你一个n个节点的多边形洞和一个半径为r，坐标为x,y的柱子（不要管高是多少=_=）。先判断这个多边形洞是不是凸多边形，如果是，则判断柱子能否放进这个洞中。

解题报告

一道挺简单的计算几何题目，题目看完了之后可以抽象为两个问题：1.该多边形是不是凸多边形。2.柱子的圆心是不是在多边形内。3.柱子是否能放入多边形中。

问题可以一个个解决，首先先来看是不是凸多边形： 对于凸多边形，pol[(i+1)%n]-pol[i]（pol[i]表示多边形第i个端点，根据向量的减法，pol[(i+1)%n]-pol[i]就是pol[i]指向pol[(i+1)%n]的向量，后面同理）和pol[(i-1+n)%n]-pol[i]的叉积都是正的，而凹多边形的叉积总会有一个是负的（因为凹多边形的某个角>π，所以叉积就会反过来），用这个特性即可判断凸多边形和凹多边形。

判断完成后，再判断柱子的圆心是否在多边形内。由于已经确定是凸多边形了，就不用用射线法或转角法了，直接判断圆心是否在凸多边形所有边的逆时针方向就行了。

最后一个问题更简单，只需要判断圆心和凸多边形所有边的距离是否都<=r即可。点到直线的距离用叉积（四边形面积）/底就可以算出。

ps：由于这道题没说多边形是按顺时针还是逆时针给出的，所以都需要判断。

示例程序

#include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int maxn=1000; double absf(double x) {if (x<0) return -x; else return x;} int fcmp(double x,double y) {if (absf(x-y)<1e-10) return 0;if (x<y) return -1; else return 1;} //减少精度问题 //============================================================================ struct Point { double x,y; Point (double X=0,double Y=0) {x=X;y=Y;} }; //点的结构体 typedef Point vec; //点和向量的表示方法是一样的，typedef一下 vec operator - (const vec &a,const vec &b) {return vec(a.x-b.x,a.y-b.y);} //向量的减法 double Dot(vec a,vec b) {return a.x*b.x+a.y*b.y;} //点积 double Length(vec a) {return sqrt(Dot(a,a));} //向量a的长度 double Cross(vec a,vec b) {return a.x*b.y-b.x*a.y;} //叉积 double distoLine(Point P,Point A,Point B) {vec a=B-A,b=P-A;return absf(Cross(a,b))/Length(a);} //P到AB的距离 //============================================================================ struct Circle { Point P; double r; }; //圆的结构体 //============================================================================ int n; Circle p; Point pol[maxn+5]; //============================================================================ bool check1() { int fl=true; for (int i=0;i<n;i++) if (fcmp(Cross(pol[(i+1)%n]-pol[i],pol[(i-1+n)%n]-pol[i]),0)<0) {fl=false;break;} //逆时针 if (fl) return true; for (int i=0;i<n;i++) if (fcmp(Cross(pol[(i-1+n)%n]-pol[i],pol[(i+1)%n]-pol[i]),0)<0) return false; //顺时针 return true; } bool check2() { int fl1=true,fl2=true; for (int i=0;i<n;i++) if (fcmp(Cross(p.P-pol[i],p.P-pol[(i+1)%n]),0)<0) {fl1=false;break;} //逆时针 for (int i=0;i<n;i++) if (fcmp(Cross(p.P-pol[(i+1)%n],p.P-pol[i]),0)<0) {fl2=false;break;} //顺时针 if (!fl1&&!fl2) return false; for (int i=0;i<n;i++) if (fcmp(distoLine(p.P,pol[i],pol[(i+1)%n]),p.r)<0) return false; return true; } int main() { freopen("program.in","r",stdin); freopen("program.out","w",stdout); for (scanf("%d",&n);n>=3;scanf("%d",&n)) { scanf("%lf%lf%lf",&p.r,&p.P.x,&p.P.y); for (int i=0;i<n;i++) scanf("%lf%lf",&pol[i].x,&pol[i].y); if (!check1()) printf("HOLE IS ILL-FORMED\n"); else if (!check2()) printf("PEG WILL NOT FIT\n"); else printf("PEG WILL FIT\n"); } return 0; }