題意：給出一個多邊形和一個圓，問是否是凸多邊形，若是則再問圓是否在凸多邊形內部。

分3步：

1、判斷是否是凸多邊形

2、判斷點是否在多邊形內部

3、判斷點到各邊的距離是否大于等于半徑

上代碼：

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> using namespace std;#define maxn 2000 #define eps 10E-8struct Point {double x, y;Point operator-(const Point &a) const{Point ret;ret.x = x - a.x;ret.y = y - a.y;return ret;} } point[maxn], peg;double pegr; int n;int dblcmp(double a) {if (fabs(a) < eps)return 0;return a >0?1 : -1; }double xmult(const Point &a, const Point &b) {return a.x * b.y - b.x * a.y; }void input() {scanf("%lf%lf%lf", &pegr, &peg.x, &peg.y);for (int i =0; i < n; i++)scanf("%lf%lf", &point[i].x, &point[i].y);int t =0;int i =0;while (i < n && t ==0){t = dblcmp(xmult(point[(i +1)%n] - point[i], point[(i +2)%n] - point[i]));i++;}if (t <0)reverse(point, point + n); }bool convex() {for (int i =0; i < n; i++)if (dblcmp(xmult(point[(i +1)%n] - point[i], point[(i +2)%n] - point[(i +1)%n])) <0)return false;return true; }bool inconvex() {for (int i =0; i < n; i++)if (dblcmp(xmult(point[(i +1)%n] - point[i], peg - point[(i +1)%n])) <=0)return false;return true; }double dist(const Point &a, const Point &b) {Point p;p = a - b;return sqrt(p.x * p.x + p.y * p.y); }bool ok() {for (int i =0; i < n; i++)if (dblcmp(abs(xmult(peg - point[i], point[(i +1)%n] - point[i]))/dist(point[i], point[(i +1)%n]) - pegr) <0)return false;return true; }int main() {while (scanf("%d", &n) != EOF){if (n<3)break;input();if (!convex())printf("HOLE IS ILL-FORMED\n");else if (!inconvex()||!ok())printf("PEG WILL NOT FIT\n");elseprintf("PEG WILL FIT\n");}return 0; }

版權聲明：本文為博主原創文章，未經博主允許不得轉載。

轉載于:https://www.cnblogs.com/wanglaoda/p/4937161.html

總結

以上是生活随笔為你收集整理的POJ 1584 A Round Peg in a Ground Hole（点到直线距离，圆与多边形相交，多边形是否为凸）...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。