題意：

按照順時針或逆時針方向輸入一個n邊形的頂點坐標集，先判斷這個n邊形是否為凸包。

再給定一個圓形（圓心坐標和半徑），判斷這個圓是否完全在n邊形內(nèi)部。

解題思路：

1、判斷該多邊形是否是凸包，由于題目已經(jīng)給定了順時針或逆時針輸入，只需判斷相鄰的三點是否是向左拐或向右拐即可，判斷的方法是向量的叉積。

2、判斷圓心是否在凸包內(nèi)，假定圓心為O，凸包上任意相鄰的兩點為Ai,Ai+1，如果O在凸包內(nèi)，則所有的OAi與OAi+1叉積應(yīng)該為同正或同負。

3、判斷整個圓是否都在凸包內(nèi)，只需判斷圓心到凸包的邊的距離是否大于等于半徑，由于是凸多邊形，所以不需要枚舉頂點。

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std;const int maxn = 105; const double eps = 1e-6; struct Point {double x,y; }p[maxn],circle; int n; double r;double Cross(Point a,Point b,Point c) { return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y); } double dis(Point a,Point b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }double mult_point(Point a,Point b,Point c) {return (a.x-c.x)*(b.x-c.x)+(a.y-c.y)*(b.y-c.y); }double GetDist(Point a,Point b,Point c) {if(dis(a,b) < eps) return dis(b,c); ///a,b是同一個點if(mult_point(b,c,a) < -eps) return dis(a,c); ///投影if(mult_point(a,c,b) < -eps) return dis(b,c);return fabs(Cross(b,c,a) / dis(a,b)); }bool isConvex() {double flag = Cross(p[1],p[2],p[3]);for(int i = 2; i <= n - 2; i++)if(flag * Cross(p[i],p[i+1],p[i+2]) < -eps) return false;if(flag * Cross(p[n-1],p[n],p[1]) < -eps) return false;return true; }bool is_In_Convex() {//判斷圓心是否在凸包內(nèi)double flag = Cross(circle,p[1],p[2]);for(int i = 1; i <= n - 1; i++)if(flag * Cross(circle,p[i],p[i+1]) < -eps) return false;if(flag * Cross(circle,p[n],p[1]) < -eps) return false;//判斷整個圓是否在凸包內(nèi)for(int i = 1; i <= n - 1; i++)if(GetDist(p[i],p[i+1],circle) - r < -eps) return false;if(GetDist(p[n],p[1],circle) - r < -eps) return false;return true; }int main() {while(scanf("%d",&n),n >= 3){scanf("%lf%lf%lf",&r,&circle.x,&circle.y);for(int i = 1; i <= n; i++)scanf("%lf%lf",&p[i].x,&p[i].y);if(isConvex() == false){printf("HOLE IS ILL-FORMED\n");continue;}if(is_In_Convex() == false)printf("PEG WILL NOT FIT\n");else printf("PEG WILL FIT\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的poj 1584(凸包+点在凸多边形内+圆在凸多边形内)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。