一道思路很简单的计算几何题目，就是先判是不是“凸多边形”，然后计算点到直线的最短距离。但是我错了很多次。一个问题就是有可能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;
}