https://atcoder.jp/contests/abc314
Ex - Disk and Segments
二维平面上 n条线段 两两无交点
求最小半径的实心圆，使得和所有线段至少一个交点
n 100
坐标 [0,1000]
2s
1024mb
我的思路
显然计算几何
都知道 圆上3点 能确定圆
但 问题是 3点不一定是 线段的端点，还可能和线段相切
想法还是 O(N^3)选择线段
那还需要 O(N)做校验
而且 选线段以后 ，是相切还是端点，似乎可以延长做三角形？
3端点 -> 定圆
2端点+1相切？
1端点+2相切？
3相切 -> 延长的三角形内切圆
另一个想法是利用坐标[0,1000]很小
如果一个方案可行，那么该方案离最近的整数点距离不超过 $(1,1) =\sqrt{2}$ , 所以整点的圆的半径和最优解的半径差不超过$\sqrt{2}$ 所以整点圆的半径也整数，和最优解差距不超过$\sqrt{2} + 1$
1
2
3
4
5
6
7
| for i in 0...1000:
# 奇
for j in 0...1000:
# 偶
for j in 1000...0:
# 圆心在i,j 的最小整数距离，注意到圆心移动不超过1,所以半径变化不超过1
O(n) 校验
|
这样的话是 1000*1000*100 感觉也不行
题解
$\displaystyle \min _ {(x,y)\in\mathbb R ^ 2}f(x,y),$
其中$f(x,y)=$圆心在$(x,y)$的圆的最小半径
性质：$f(x,y)$ 是凸的！
证明：
引理1: $d_p(x,y)$ 表示点$(x,y)$到点p的距离， 它是凸的, 显然锥体样子
引理2: $d_s(x,y)$ 表示点$(x,y)$到线段s的距离， 它是凸的，显然像是锥体一分为二拉长
引理3: $g_i(x,y)$ 表示一个平面凸包函数，那么$g(x,y)=\max g_i(x,y)$ 也是凸的！
这引理3我自己没想出来，目标是证明$g((1-t)a+tb)\le (1-t)g(a)+tg(b),\forall a,b\in \mathbb{R}^2,0\le t\le 1$
证明: 对于$\forall a,b\in \mathbb{R}^2, 0\le t\le 1$存在$i$
$g((1-t)a+tb) = g_i((1-t)a+tb) \le (1-t)g_i(a)+tg_i(b) \le (1-t)g(a)+tg(b)$
得证
容易证明 在二维上是 convex,那么固定一个维度，另一个单独维度也是convex
令 $F(x):=\min_{y\in \mathbb{R}} f(x,y)$
证明 $F(x)$也是 凸的
直接2维对应证明，对于$\forall x_0,x_1$, 它们对应的 $\min y_0,\min y_1$, 那么直接在二维定义域上有线段
$(x_0,y_0,z_0) \to (x_1,y_1,z_1)$, 而注意到二维上是凸的，所以 面在该线段下方，而该线段对应的面的值$\ge F(p)$ , p是((线段上的点的$(x,y)$对应的)面上的点)
因此证明了 $F(x)$也是凸的
因此双维度交替 三分 就完了
然后如果圆心在 [0,1000]x[0,1000]外，那么把它沿着坐标轴，圆心平移到最近边界上，一定覆盖更多不会更差，所以圆心范围在上面范围内
代码
https://atcoder.jp/contests/abc314/submissions/49588250
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
63
64
65
66
67
68
69
70
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
ll read(){ll r;scanf("%lld",&r);return r;}
using Real = double;
using point_type = tuple<Real, Real>;
using segment_type = tuple<point_type,point_type>;
using arrow_type = tuple<Real, Real>;
arrow_type operator-(const point_type&p0, const point_type&p1){
const auto&[x0, y0]{p0};
const auto&[x1, y1]{p1};
return {x0-x1,y0-y1};
};
Real dot(const arrow_type&a0, const arrow_type&a1){
const auto&[x0, y0]{a0};
const auto&[x1, y1]{a1};
return x0*x1+y0*y1;
};
Real cross(const arrow_type&a0, const arrow_type&a1){
const auto&[x0, y0]{a0};
const auto&[x1, y1]{a1};
return x0*y1-x1*y0;
};
int main() {
int n = read();;
vector<segment_type> segments;
rep(i,0,n) segments.push_back({{read(),read()},{read(),read()}});
const auto distance_point_and_point{[](const point_type &p0, const point_type &p1) {
const auto&[x0, y0]{p0};
const auto&[x1, y1]{p1};
return hypot(x0 - x1, y0 - y1);
}};
const auto distance_segment_and_point{[&](const segment_type &segment, const point_type &p) {
const auto&[p0,p1]{segment};
if (dot(p1-p0,p-p0) < 0) return distance_point_and_point(p0,p);
if (dot(p0-p1,p-p1) < 0) return distance_point_and_point(p1,p);
return abs(cross(p1-p0,p-p0)) / distance_point_and_point(p0,p1);
}};
const auto minimum_crossing_circle{[&](const point_type &point) {
Real ret{};
for(const auto& segment : segments) ret = max(ret, distance_segment_and_point(segment, point));
return ret;
}};
const auto minimize_unimodal_function{[](Real L, Real R, auto &&function) {
rep(_,0,100) {
auto M1{(L * 2 + R) / 3};
auto M2{(L + 2 * R) / 3};
if (function(M1) < function(M2)){
R = M2;
}else{
L = M1;
}
}
return function(L);
}};
printf("%.15lf\n", minimize_unimodal_function(0, 1000, [&](auto x) {
return minimize_unimodal_function(0, 1000, [&](auto y) {
return minimum_crossing_circle({x, y});
});
}));
return 0;
}
|
参考
https://atcoder.jp/contests/abc314/editorial
总结
凸性的目标式，只熟悉了$f:\mathbb{R}\to \mathbb{R}$的，没有熟悉这种自变量是$\mathbb{R}^2$的，但实际上本质没有区别，从变量角度，看成一个变量(点坐标)就行了
然后虽然这题是计算几何，但是核心还是凸函数写的性质，看上去似乎可以往更高维度的定义域推也是对的
官方代码似乎已经用上C++20, ranges::views::iota, 各种auto,
https://en.cppreference.com/w/cpp/ranges/iota_view
返回 平方和的平方根 hypot(a,b):c
1
| const auto&[x, y]{point0};
|