【题解】袭击

题目链接

题目描述

在与联盟的战斗中屡战屡败后，帝国撤退到了最后一个据点。

依靠其强大的防御系统，帝国击退了联盟的六波猛烈进攻。

经过几天的苦思冥想，联盟将军亚瑟终于注意到帝国防御系统唯一的弱点就是能源供应。

该系统由 \(N\) 个核电站供应能源，其中任何一个被摧毁都会使防御系统失效。

将军派出了 \(N\) 个特工进入据点之中，打算对能源站展开一次突袭。

不幸的是，由于受到了帝国空军的袭击，他们未能降落在预期位置。

作为一名经验丰富的将军，亚瑟很快意识到他需要重新安排突袭计划。

他现在最想知道的事情就是哪个特工距离其中任意一个发电站的距离最短。

你能帮他算出来这最短的距离是多少吗？

输入格式

输入中包含多组测试用例。

第一行输入整数 \(T\) ，代表测试用例的数量。

对于每个测试用例，第一行输入整数 \(N\) 。

接下来N行，每行输入两个整数 \(X\) 和 \(Y\)，代表每个核电站的位置的 \(X\) ，\(Y\) 坐标。

在接下来N行，每行输入两个整数X和Y，代表每名特工的位置的X，Y坐标。

输出格式

每个测试用例，输出一个最短距离值，结果保留三位小数。

每个输出结果占一行。

样例

样例输入

2
4
0 0
0 1
1 0
1 1
2 2
2 3
3 2
3 3
4
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0


样例输出

1.414
0.000


数据范围与提示

\(1\le N\le100000\)

\(0\le X,Y\le1000000000\)

Solution

分治。（不要问我怎么知道的）

铺垫 题解

好了，等你看完上面的部分，这题最妙的部分就不用我讲了，我就没事干了，本文终结。

对于同一个分组，它的最近点对我们可以这样求解：

将它按 \(x\) 优先， \(y\) 其次的规则从小到大排序，凡是看到关于坐标的不简单题，是个人都会先把 \(\operatorname{sort}\) 写上。可惜我不是人

那么，现在这个数组已经从左到右排好了，我们把它分成两半截。开始盗图

假设我们已经求出来了 \([left,mid]\) 的答案和 \([mid+1,right]\) 的答案，我们用 \(d\) （也就是记录答案的变量）记录它们的 \(\min\) 值。

但四！可爱的孩纸们，难道距离最近的就不可能在中间那一段吗？

在上图中：

• 蓝色+紫色为答案可能区间1( \([left,mid]\) )


• 紫色+橙色为答案可能区间2( 将求的值 )


• 橙色+绿色为答案可能区间3( \([mid+1,right]\) )

那么，区间2如何处理呢？

上图中，紫色和橙色长方形的宽都是 \(d\)，为什么呢？因为只有当它们的距离在 \(d\) 范围内， \(d\) 才有可能被更新，所以我们只用计算 \(l\) ~ \(r\) 中，\(x\) 坐标在 \([mid-d,mid+d]\) 范围内的点就行啦！

把满足上述要求的点放在 \(tmp\) 数组中，由于这个数组本身已经在范围内了，此时我们按 \(y\) 坐标排序，这样便于找到与某个点距离最近的点。

枚举 \(tmp\) 中的每一对点。当这一对点的 \(y\) 坐标的距离大于 \(d\) 时，我们就可以 \(break\) 掉了。因为已经按 \(y\) 坐标排好序， \(y\) 小的点太远，更大的自然不行。

但，这只是同一个分组的情况。不同分组其实也没有什么不同，就是在求距离的时候判一下就行了。

综上所述。。。

Code

#include
#include
#include
#include
using std::sort;
typedef double db;
const int maxn=1e5+5;
const db inf=DBL_MAX;
struct node{
db x,y;
bool type;
db operator-(const node q)const{
if(type==q.type)return inf;
return sqrt((x-q.x)*(x-q.x)+(y-q.y)*(y-q.y));
}
}a[maxn],tmp[maxn];
int T,n;
bool cmpx(node x,node y){
return x.x==y.x?x.y}
bool cmpy(node x,node y){
return x.y==y.y&&x.x}
db min(db x,db y){
return x}
db max(db x,db y){
return x>y?x:y;
}
db ll45l4(int l,int r){ //恶臭函数名
if(r-l<=1)return a[r]-a[l];
int mid=l+r>>1,cnt=0;
db d=min(ll45l4(l,mid),ll45l4(mid+1,r));
for(int i=l;i<=r;++i){
if(a[mid].x-d<=a[i].x&&a[mid].x+d>=a[i].x)
tmp[++cnt]=a[i];
}
sort(tmp+1,tmp+cnt+1,cmpy);
for(int i=1;i<=cnt;++i){
for(int j=i+1;j<=cnt;++j){
if(a[j].y-a[i].y>d)break;
d=min(d,a[i]-a[j]);
}
}
return d;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%lf%lf",&a[i].x,&a[i].y);
a[i].type=0;
}
for(int i=1;i<=n;++i){
scanf("%lf%lf",&a[n+i].x,&a[n+i].y);
a[i].type=1;
}
n<<=1;
sort(a+1,a+n+1,cmpx);
printf("%.3lf\n",ll45l4(1,n));
}
return 0;
}


end.

—— · EOF · ——

千里之行，始于足下