Description
很久以前，在世界的某处有一个形状为凸多边形的小岛，岛上的居民们决定建一个祭坛，居民们任务祭坛的位置离岛的顶点处越远越好。 你的任务是求凸多边形内一点，使其与各顶点的距离中最短的距离最远，点在边上也可以。 这样的点可能有多个，你只需输出这些点与各顶点的最短距离。
第一行是一个整数N(3<=N<=100)。 接下来N行按逆时针顺序给出每个顶点的坐标，每行包含2个实数，表示顶点的横坐标和纵坐标（坐标绝对值小于10000）。
Output
输出一个实数，表示凸多边形内一点与各顶点的距离中最短的距离的最大值（保留三位小数）。
Sample Output
题目大意
给出一个多边形，最大化一个点到各顶点的最短的距离，求最大化的最短距离
题解
从样例入手
此时，最大化的最短距离为这个三角形的外接圆的半径
这启示我们从圆入手
看到最大，最小，想到二分答案ans
检验一个答案ans是否正确，可以以每个顶点为圆心，ans长为半径画弧，交多边形的边
假设当前的ans为3，那样例就变成了这样
此时发现区域c，是没有被扇形覆盖的，由此可见，此时的ans=4是合法的
做一点简单的观察，E，F，I，H，D点到A，B，C点的距离都大于ans（由图易得）
这又启示我们从任意两点构造出来的扇形的交点来判断ans的合法性
于是有了一些难点：
第一个是求扇形的交点
对于两个点A，B，有BD=AD=BE=AE=ans，则DE垂直平分AB
过D做水平竖直的线，易证△DGF∼△BCA
由勾股定理，DF已知，由此可知DG，GF，
又知中点F的坐标，因此可求交点D坐标
同理得E
第二个是没有交点
没有交点的话把G，H，（扇形与多边形边的交点）当成交点就好啦
也是可以用相似求出点坐标的
第三个是判断扇形的交点是否在多边形以内
计算多边形的面积为S
对于一个点E，我们计算它与多边形的每一条边连成的三角形的面积的总和sum
显然，在第一个图中，E在多边形的内部，sum=S
在第二个图中，E在多边形的外部，sum>S
由此可以判断，扇形的交点是否在多边形内。
然后就没有啦~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include <cmath>
#include <cstdio>
#define sqr(x) ((x)*(x))
#define dis(u,v,r,s) sqrt(sqr(u - r) + sqr(v - s))
using namespace std;
double l, r, mid, S, x[105], y[105]; int n;
double size(double u, double v, int i, int j) {
double t1 = (x[j] - x[i]), t2 = (y[j] - y[i]);
double r = (t1 * t1 * u + t2 * t2 * x[i] + v * t1 * t2 - y[i] * t2 * t1) / (t2 * t2 + t1 * t1);
double s = !t2 ? y[i] : -t1 * (r - u) / t2 + v;
double h = dis(u, v, r, s), d = sqrt(t1 * t1 + t2 * t2);
return (h * d / 2);
}
bool in(double u, double v) {
double sum = 0;
for (int i = 1; i <= n; ++i)
sum += size(u, v, i, i % n + 1);
return abs(S - sum) <= 10e-6;
}
bool check(double u, double v, double a) {
for (int k = 1; k <= n; ++k)
if (dis(u, v, x[k], y[k]) < a)
return 0; return 1;
}
bool ok(double a) {
for (int i = 1; i < n; ++i)
for (int j = i + 1; j <= n; ++j) {
double u = x[i] - x[j], x1, y1;
double v = y[i] - y[j], x2, y2;
double c = sqrt(u * u + v * v);
if (a < c / 2) {
x1 = x[j] + u * a / c, y1 = y[j] + v * a / c;
x2 = x[i] - u * a / c, y2 = y[i] - v * a / c;
} else {
double h = sqrt(a * a - c * c / 4);
x1 = (x[i] + x[j]) / 2 + v * h / c;
y1 = (y[i] + y[j]) / 2 - u * h / c;
x2 = (x[i] + x[j]) / 2 - v * h / c;
y2 = (y[i] + y[j]) / 2 + u * h / c;
}
if (in(x1, y1) && check(x1, y1, a)) return 1;
if (in(x2, y2) && check(x2, y2, a)) return 1;
}
return 0;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%lf%lf", x + i, y + i);
for (int i = 1; i < n; ++i)
for (int j = i + 1; j <= n; ++j) {
double t = dis(x[i],y[i],x[j],y[j]);
if (t > r) r = t;
}
for (int i = 1; i < n - 1; ++i)
S += size(x[n], y[n], i, i + 1);
while (l + 10e-6 < r) {
mid = (l + r) / 2;
if (ok(mid)) l = mid; else r = mid;
}printf("%.3lf", l);
}
|
