這個(gè)題需要多個(gè)計(jì)算幾何算法。第一個(gè)是判斷一系列點(diǎn)是否能夠構(gòu)成凸多邊形，第二個(gè)是判斷一個(gè)點(diǎn)是否在一個(gè)簡單多邊形內(nèi)部，
其實(shí)，我是要判斷一個(gè)圓是否則一個(gè)凸多邊形內(nèi)部而用到算法二和三。其實(shí)，有不需要判斷圓心是否則多邊形內(nèi)部的算法。
算法一的思想，求所有邊的偏轉(zhuǎn)方向，必須都是逆時(shí)針或者順時(shí)針偏轉(zhuǎn)。算法二則是我前面發(fā)的那篇改進(jìn)弧長法判斷點(diǎn)和多邊形的關(guān)系，
算法三尤其簡單，直線上面取2點(diǎn)，用叉積求出這三點(diǎn)構(gòu)成的三角形面積的2倍，再除以底邊。算法四則是先判斷圓心在多邊形內(nèi)部，然后
#include <stdio.h>
#include <
string.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
const double fPre = 1e-8;
int DblCmp(
double fD)
{
if (fabs(fD) < fPre)
{
return 0;
}
else {
return fD > 0 ? 1 : -1;
}
}
struct Point
{
double x, y;
bool operator == (
const Point& p)
{
return DblCmp(x - p.x) == 0 && DblCmp(y - p.y) == 0;
}
};
Point
operator-(
const Point& a,
const Point& b)
{
Point p;
p.x = a.x - b.x;
p.y = a.y - b.y;
return p;
}
double Det(
double fX1,
double fY1,
double fX2,
double fY2)
{
return fX1 * fY2 - fX2 * fY1;
}
double Cross(Point a, Point b, Point c)
{
return Det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}
bool IsConvexPolygon(vector<Point>& vp)
{
int nN = vp.size();
int nDirection = 0;
bool bLine =
true;
//避免所有點(diǎn)共線
for (
int i = 0; i < nN; ++i)
{
int nTemp = DblCmp(Cross(vp[i], vp[(i + 1) % nN], vp[(i + 2) % nN]));
if (nTemp)
{
bLine =
false;
}
//這次的方向和上次的方向必須是相同的或者是3點(diǎn)和3點(diǎn)以上共線的情況
if (nDirection * nTemp < 0)
{
return false;
}
nDirection = nTemp;
}
return bLine ==
false;
}
int GetQuadrant(Point p)
{
return p.x >= 0 ? (p.y >= 0 ? 0 : 3) : (p.y >= 0 ? 1 : 2);
}
bool IsPtInPolygon(vector<Point>& vp, Point p)
{
int nN = vp.size();
int nA1, nA2, nSum = 0;
int i;
nA1 = GetQuadrant(vp[0] - p);
for (i = 0; i < nN; ++i)
{
int j = (i + 1) % nN;
if (vp[i] == p)
{
break;
}
int nC = DblCmp(Cross(p, vp[i], vp[j]));
int nT1 = DblCmp((vp[i].x - p.x) * (vp[j].x - p.x));
int nT2 = DblCmp((vp[i].y - p.y) * (vp[j].y - p.y));
if (!nC && nT1 <= 0 && nT2 <= 0)
{
break;
}
nA2 = GetQuadrant(vp[j] - p);
switch ((nA2 - nA1 + 4) % 4)
{
case 1:
nSum++;
break;
case 2:
if (nC > 0)
{
nSum += 2;
}
else {
nSum -= 2;
}
break;
case 3:
nSum--;
break;
}
nA1 = nA2;
}
if (i < nN || nSum)
{
return true;
}
return false;
}
double PtDis(Point a, Point b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (b.y - a.y) * (b.y - a.y));
}
//點(diǎn)p到直線ab的距離
//h = (2 * Spab) / |ab|
double GetDis(Point a, Point b, Point p)
{
return fabs(Cross(a, b, p)) / PtDis(a, b);
}
bool IsCircleInPolygon(vector<Point>& vp, Point p,
double fR)
{
if (!IsPtInPolygon(vp, p))
{
return false;
}
int nN = vp.size();
for (
int i = 0; i < nN; ++i)
{
if (GetDis(vp[i], vp[(i + 1) % nN], p) < fR)
{
return false;
}
}
return true;
}
int main()
{
int nN;
double fR, fPx, fPy;
vector<Point> vp;
Point p;
while (scanf("%d%lf%lf%lf", &nN, &fR, &fPx, &fPy), nN >= 3)
{
vp.clear();
for (
int i = 0; i < nN; ++i)
{
scanf("%lf%lf", &p.x, &p.y);
vp.push_back(p);
}
if (IsConvexPolygon(vp))
{
p.x = fPx;
p.y = fPy;
if (IsCircleInPolygon(vp, p, fR))
{
printf("PEG WILL FIT\n");
}
else {
printf("PEG WILL NOT FIT\n");
}
}
else {
printf("HOLE IS ILL-FORMED\n");
}
}
return 0;
}