题面：Raid
题目大意
有 N 个核电站能源供应点需要被摧毁。 将军派出了 N 位特工去摧毁这些供应点。 由于受到了帝国空军的袭击，特工分散到了几个位置，每个位置有坐标给出。 将军想哪个特工离任意一个核电站的距离最小。 请你求出这个最小距离。
思路
分治。 将所有点按
x
x
x 坐标从小到大先排好序，之后可以分成左右两部分进行分别的计算最短距离，再进行计算中间部分可能的最短距离。但是这题是由两个不同的阵营组成，我们可以先将阵营标记出来，同阵营之间的距离就给赋值成 “无穷大”。
左右两边我们只要运用归并的思想分别去递归计算就可以了，
y
y
y 坐标也进行一下相应的归并排序。 对于中间部分，设当前区间的
x
x
x 坐标的中间值为
m
i
d
x
midx
midx，前面已经求出了左右两边的最短距离，设为
m
i
n
_
d
i
s
t
min\_dist
min_dist。那么如果需要更新距离的最小值，则中间的点需要在区间
[
m
i
d
x
−
m
i
n
_
d
i
s
t
,
m
i
d
x
+
m
i
n
_
d
i
s
t
]
[midx-min\_dist,midx+min\_dist]
[midx−min_dist,midx+min_dist] 上。 如下图所示： 这样我们只需要考虑在区间内的每个点和点对应的阴影区域内的点的距离就行了。如果有符合条件的，则可以更新
m
i
n
_
d
i
s
t
min\_dist
min_dist 的值。
这里有一个很强的性质，使得我们可以在
O
(
n
)
O(n)
O(n) 的时间复杂度内求出中间左边一个点对应右边某点的情况。 这个性质是：每处理一个左边的点时，右边最多只会有
6
6
6 个点被考虑到。
最终算法的时间复杂度为
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)。如果不对
y
y
y 坐标进行归并排序的话，最坏时间复杂度可能会到
O
(
n
2
)
O(n^2)
O(n2)。
性质证明：
我们先考虑一下极端的情况，即选择的点刚好在中线上，如下图： 由于右半边是个半圆，不是很好进行计算，我们可以将右半边化成一个六等分的矩形，如下图： 假设在这矩形内有七个点，那么由于抽屉原理，至少有两个点在同一个六等分矩形内。 不妨假设右上角那个矩形中有两个点。 易知，两个点之间的距离一定会小于该小矩形的对角线长度。 对角线长度为：
(
1
2
r
)
2
+
(
2
3
r
)
2
=
r
∗
1
4
+
4
9
=
5
6
r
<
r
\sqrt{(\cfrac{1}{2}r)^2+(\cfrac{2}{3}r)^2}=r*\sqrt{\cfrac{1}{4}+\cfrac{4}{9}}=\cfrac{5}{6}r<r
(21r)2+(32r)2
=r∗41+94
=65r<r。
所以，很明显是与上述
m
i
n
_
d
i
s
t
min\_dist
min_dist 是从左右两边选出来的最短距离是违背的。
因此，每一个左边的点所对应的阴影区域内的点不会超过六个点。
代码
#include <bits/stdc++.h>
#define sc scanf
#define pf printf
using namespace std
;
const double INF
= 1e10;
const int N
= 1e5 + 10;
struct Point
{
double x
, y
;
bool type
;
bool operator<(const Point
&T
) const
{
return x
< T
.x
;
}
}p
[N
], temp
[N
];
double dist(Point a
, Point b
)
{
if(a
.type
== b
.type
) return INF
;
double dx
= a
.x
- b
.x
, dy
= a
.y
- b
.y
;
return sqrt(dx
* dx
+ dy
* dy
);
}
double dfs(int l
, int r
)
{
if(l
>= r
) return INF
;
int mid
= l
+ r
>> 1;
double mid_x
= p
[mid
].x
;
double res
= min(dfs(l
, mid
), dfs(mid
+ 1, r
));
{
int k
= 0, i
= l
, j
= mid
+ 1;
while(i
<= mid
&& j
<= r
)
if(p
[i
].y
<= p
[j
].y
) temp
[k
++] = p
[i
++];
else temp
[k
++] = p
[j
++];
while(i
<= mid
) temp
[k
++] = p
[i
++];
while(j
<= r
) temp
[k
++] = p
[j
++];
for(i
= l
, j
= 0; i
<= r
; i
++, j
++) p
[i
] = temp
[j
];
}
int k
= 0;
for(int i
= l
; i
<= r
; i
++)
if(p
[i
].x
>= mid_x
- res
&& p
[i
].x
<= mid_x
+ res
)
temp
[k
++] = p
[i
];
for(int i
= 0; i
< k
; i
++)
for(int j
= i
- 1; j
>= 0 && temp
[i
].y
- temp
[j
].y
<= res
; j
--)
res
= min(res
, dist(temp
[i
], temp
[j
]));
return res
;
}
void solve()
{
int n
;
sc("%d", &n
);
for(int i
= 0; i
< n
; i
++) {
sc("%lf %lf", &p
[i
].x
, &p
[i
].y
);
p
[i
].type
= false;
}
for(int i
= n
; i
< 2 * n
; i
++) {
sc("%lf %lf", &p
[i
].x
, &p
[i
].y
);
p
[i
].type
= true;
}
sort(p
, p
+ 2 * n
);
pf("%.3f\n", dfs(0, 2 * n
- 1));
return ;
}
int main()
{
int t
; sc("%d", &t
); while(t
--) solve();
return 0;
}
