poj2352，poj1584

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

poj2352、分析：計算幾何

分3步：

1、判斷是否是凸多邊形

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

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

首先，若點是順時針則reverse()改為逆時針，reverse函數就是用來把數組反向的。然后利用每3個相鄰點組成的兩條向量的叉積來判斷，都應大于等于零。然后，判斷是否在內部，利用釘子點和多邊形每兩個相鄰點，組成兩個向量。判斷叉積是否全都大于0（全為逆時針）。再就是判斷點到直線的距離，利用三角形面積除以底邊，面積用叉積求。

 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
usingnamespace std;

#define maxn 2000
#define eps 10E-9

struct 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)
return0;
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)
returnfalse;
returntrue;
}

bool inconvex()
{
for (int i =0; i < n; i++)
if (dblcmp(xmult(point[(i +1)%n] - point[i], peg - point[(i +1)%n])) <=0)
returnfalse;
returntrue;
}

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)
returnfalse;
returntrue;
}

int main()
{
//freopen("t.txt", "r", stdin);
while (scanf("%d", &n) != EOF)
 {
if (n <3)
break;
 input();
if (!convex())
 printf("HOLE IS ILL-FORMED\n");
elseif (!inconvex()||!ok())
 printf("PEG WILL NOT FIT\n");
else
 printf("PEG WILL FIT\n");
 }
return0;
}