题目描述
在与联盟的战斗中屡战屡败后,帝国撤退到了最后一个据点。
依靠其强大的防御系统,帝国击退了联盟的六波猛烈进攻。
经过几天的苦思冥想,联盟将军亚瑟终于注意到帝国防御系统唯一的弱点就是能源供应。
该系统由 N 个核电站供应能源,其中任何一个被摧毁都会使防御系统失效。
将军派出了 N 个特工进入据点之中,打算对能源站展开一次突袭。
不幸的是,由于受到了帝国空军的袭击,他们未能降落在预期位置。
作为一名经验丰富的将军,亚瑟很快意识到他需要重新安排突袭计划。
他现在最想知道的事情就是哪个特工距离其中任意一个发电站的距离最短。
你能帮他算出来这最短的距离是多少吗?
输入格式
输入中包含多组测试用例。
第一行输入整数 T,代表测试用例的数量。
对于每个测试用例,第一行输入整数 N。
接下来 N 行,每行输入两个整数 X 和 Y,代表每个核电站的位置的 X,Y 坐标。
在接下来 N 行,每行输入两个整数 X 和 Y,代表每名特工的位置的 X,Y 坐标。
输出格式
每个测试用例,输出一个最短距离值,结果保留三位小数。
每个输出结果占一行。
数据范围
1≤N≤100000,
0≤X,Y≤1000000000
样例
输入样例
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
本篇题解主要是想写一下如何AC加强后的数据。
我在提交过程中发现本题应该是被加强了两次。
第一次加强是十万个(0,0)点,这个数据我在讨论区中找到了解法:
可以从这里看一下https://www.acwing.com/problem/content/discussion/content/2743/
但是这个解法被提出后,很快就被hack了,数据是位于y轴上的一列数:
下半边是A组,上半边是B组。
这导致在分治时,除了最后一次将两组数混合在了一起,其余情况均是A组在一起,B组在一起。
这就导致每次计算答案都会将所有点考虑在内。
解决思路:
1.刚开始想过对所有点旋转一个角度,但是后来发现这并不能使两组点混合在一起。
2.给每个点加一个随机数,排序时若横坐标相同,则按随机数排序。
在所有点的横坐标相同的情况下,加上随机数,就可以使所有点混合,从而避免了将所有点考虑在内的情况。
下面的代码是用rand写的,大家也可以手写一个hash函数,只要给每个点一个随机数即可。
C++ 代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+10,mod = 16603;
const double INF = 1e18,eps=1e-6;
struct Node{
double x,y;
int type;
int rd;
bool operator<(const Node&nd){
if(fabs(x-nd.x)<eps)return rd<nd.rd;
return x<nd.x;
}
}point[N<<1],tmp[N<<1];
int T,n;
double mx=INF;
double th;
double dis(Node a,Node b){
if(a.type==b.type)return mx;
double dx=a.x-b.x,dy=a.y-b.y;
double res=sqrt(dx*dx+dy*dy);
mx=min(res,mx);
return res;
}
double dfs(int l,int r){
if(l>=r)return mx;
int mid=l+r>>1;
double mid_x=point[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(point[i].y<=point[j].y)tmp[k++]=point[i++];
else tmp[k++]=point[j++];
}
while(i<=mid)tmp[k++]=point[i++];
while(j<=r)tmp[k++]=point[j++];
for(i=l,k=0;i<=r;i++,k++)point[i]=tmp[k];
}
int k=0;
for(int i=l;i<=r;i++){
if(point[i].x>mid_x-res&&point[i].x<mid_x+res)tmp[k++]=point[i];
}
for(int i=0;i<k;i++){
for(int j=i+1;j<k&&tmp[j].y-tmp[i].y<res;j++){
res=min(res,dis(tmp[i],tmp[j]));
}
}
return res;
}
void solve(){
mx=INF;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf%lf",&point[i].x,&point[i].y);
point[i].rd=rand()%1000000;
point[i].type=0;
}
for(int i=n+1;i<=2*n;i++){
scanf("%lf%lf",&point[i].x,&point[i].y);
point[i].rd=rand()%1000000;
point[i].type=1;
}
mx=min(mx,dis(point[1],point[2*n]));
sort(point+1,point+1+2*n);
printf("%.3lf\n",dfs(1,2*n));
}
int main(){
srand(0);
scanf("%d",&T);
while(T--)solve();
return 0;
}
hack,如果有两列(i!=j),左边一列是type=0,右边是type=1 ,这样就没法混合了吧?
强
orz
强👍
ok,确实多个=,3q
for(int i=0;i<k;i){
for(int j=i+1;j<k&&tmp[j].y-tmp[i].y<res;j){
res=min(res,dis(tmp[i],tmp[j]));
}
}
佬,第二层循环改为i=i-1,i–,这样往前循环就会超时。百思不得其解
倒着循环是可以的,你可能条件没改全,j>=0&&tmp[i].y-tmp[j].y<res