题解：P10459 Raid

a18981826590 · 2024-08-23 19:44:28 · 题解

P10459 Raid

解题思路

致敬 P1429 平面最近点对（加强版）的大佬们！

我们充分发扬人类智慧：

将所有的电站和特工分别按 x 坐标和 y 坐标排序

根据数学直觉，在排序后，电站和特工在数组中肯定不会离得太远

所以我们只取每个特工向前和向后的 65 个电站来计算答案

这样速度快得飞起，在 n=100000 时都可以在 47ms 内卡过

AC 代码

#include<bits/stdc++.h>
using namespace std;
struct f{
    long long int x,y;
}a[100010],b[100010];
int m,n;
long long int s;
inline int read(){
    char c;
    int d=0,e=1;
    c=getchar_unlocked();
    while(!isdigit(c)){
        if(c=='-') e=-1;
        c=getchar_unlocked();
    }
    while(isdigit(c)){
        d=(d<<1)+(d<<3)+(c^48);
        c=getchar_unlocked();
    }
    return d*e;
}
bool g(f p,f q){
    return p.x<q.x;
}
bool h(f p,f q){
    return p.y<q.y;
}
long long int z(int p,int q){
    return (b[p].x-a[q].x)*(b[p].x-a[q].x)+(b[p].y-a[q].y)*(b[p].y-a[q].y);
}
int main(){
    m=read();
    while(m--){
        n=read();
        s=LONG_LONG_MAX;
        for(int i=0;i<n;i++){
            a[i].x=read();
            a[i].y=read();
        }
        for(int i=0;i<n;i++){
            b[i].x=read();
            b[i].y=read();
        }
        sort(a,a+n,g);
        sort(b,b+n,g);
        for(int i=0;i<n;i++){
            for(int j=max(0,i-65);j<min(n,i+66);j++) s=min(s,z(i,j));
        }
        sort(a,a+n,h);
        sort(b,b+n,h);
        for(int i=0;i<n;i++){
            for(int j=max(0,i-65);j<min(n,i+66);j++) s=min(s,z(i,j));
        }
        printf("%.3f\n",sqrt(1.0*s));
    }
    return 0;
}