一道思路很簡單的計算幾何題目，就是先判是不是“凸多邊形”，然后計算點到直線的最短距離。但是我錯了很多次。一個問題就是有可能peg不在多邊形內，這要單獨判斷一下；還有一個問題找了很久才發現，原來題目中說滿足條件的多邊形不是純粹的凸多邊形，題目中的多邊形是“任意內部兩點連線不會和多邊形的邊相交”，這樣如果多邊形的多個頂點存在共線的情況，其實也是可以的，但是我誤以為就是正常的凸多邊形，結果狂WA
以后讀題還是得仔細啊，考慮問題要全面。。
PKU 1584
#include <cstdio>
#include <cmath>
const int N = 128;
const double eps = 1e-6, PI = acos(-1.0);
struct point
{
double x, y;
point operator - (const point &p)const
{
point tmp;
tmp.x = x - p.x;
tmp.y = y - p.y;
return tmp;
}
double operator * (const point &p)const
{
return x * p.y - y * p.x;
}
};
int dblcmp(double a)
{
if (fabs(a) < eps) return 0;
return a > 0 ? 1 : -1;
}
double dot(const point &p1, const point &p2)
{
return p1.x * p2.x + p1.y * p2.y;
}
double relation(const point &a, const point &b, const point &c)
{
return dot(c - a, b - a) / ((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}
point perpendicular(const point &a, const point &b, const point &c)
{
double r;
point p;
r = relation(a, b, c);
p.x = (1.0 - r) * a.x + r * b.x;
p.y = (1.0 - r) * a.y + r * b.y;
return p;
}
double angel(const point &o, const point &a, const point &e)
{
point oa, oe;
double r, up, down;
oa = a - o;
oe = e - o;
up = oa.x * oe.x + oa.y * oe.y;
down = (oa.x * oa.x + oa.y * oa.y) * (oe.x * oe.x + oe.y * oe.y);
r = up / sqrt(down);
if (r >= 1.0)
return 0;
if (r <= -1.0)
return -1.0 * PI;
/**//*3點共線情況*/
if (dblcmp((a - o) * (e - o)) > 0) //判方向
return acos(r);
else
return -1.0 * acos(r);
}
int pointInPolygon(point pointset[], int n, point p)
{
double a = 0;
for (int i = 0; i < n; i++)
{
double tmp = dblcmp((pointset[i] - p) * (pointset[(i+1)%n] - p));
if (tmp != 0)
a += angel(p, pointset[i], pointset[(i+1)%n]);
}
if (dblcmp(a) == 0) //點在外轉角和為0
return 0;
else if (dblcmp(fabs(a) - 2.0 * PI) == 0) //點在內轉角和為2*PI
return 2;
else
return 1;
}
double dis(const point &p1, const point &p2)
{
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
double pointToSegment(const point &a, const point &b, const point &c)
{
point p;
if (relation(a, b, c) <= 0)
return dis(a, c);
else if (relation(a, b, c) >= 1)
return dis(b, c);
else
{
p = perpendicular(a, b, c);
return dis(p, c);
}
}
bool is_convex(point p[N], int n)
{
double tmp = (p[1] - p[0]) * (p[2] - p[0]);
for (int i = 1; i < n; i++)
if (dblcmp((p[(i+1)%n] - p[i]) * (p[(i+2)%n] - p[i]) * tmp) < 0)
return false;
return true;
}
int main()
{
int n, i;
double r;
point peg, p[N];
while (scanf("%d", &n) == 1 && n >= 3)
{
scanf("%lf %lf %lf", &r, &peg.x, &peg.y);
for (i = 0; i < n; i++)
scanf("%lf %lf", &p[i].x, &p[i].y);
if (!is_convex(p, n))
{
puts("HOLE IS ILL-FORMED");
continue;
}
for (i = 0; i < n; i++)
if (dblcmp(pointToSegment(p[i], p[(i+1)%n], peg) - r) < 0)
break;
printf("%s\n", i == n && pointInPolygon(p, n, peg) == 2 ? "PEG WILL FIT" : "PEG WILL NOT FIT");
}
return 0;
}