题解：P10459 Raid

· · 题解

一道经典的人类智慧题，按照 x \cdot y 排序，由直觉最近点对在数组中的距离较近，所以枚举每个点的后 j 个点即可。
这样容易被卡，考虑旋转随机角度 \alpha，对于位于 (x,y) 的点，旋转后位于 (x \cdot \cos \alpha - y \cdot \sin \alpha,x \cdot \sin \alpha + y \cdot \cos \alpha)。
与此同时，为了避免 Perfect_Youth 的 hack，正确性上将原本的固定旋转角度改为随机。
此外，为了防止代码在极限数据下超时，使用快读。
未使用快读时 j 取到 100 时就要花费 900 毫秒，添加后取 500 也能过。
此时我们被伟大的管理员卡掉了，然后我们惊喜的发现不旋转能过。

#include<bits/stdc++.h>
using namespace std;
#ifdef ONLINE_JUDGE
char buf[1 << 23] , * p1 = buf , * p2 = buf , obuf[1 << 23] , * O = obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
inline int read() {
    int x = 0 , f = 1;char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') f = -1;ch = getchar(); }
    while (isdigit(ch)) x = x * 10 + (ch ^ 48) , ch = getchar();
    return x * f;
}
int t,n;
long double ans=10000000000,deg,tx,ty;
struct node{long double x,y,t;}a[400010];
long double dis(node x,node y){return sqrtl((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));}
bool cmp(node x,node y){return x.x*x.y<y.x*y.y;}
int main()
{
    ios::sync_with_stdio(0);
    t=read();
    srand(time(0));
//  deg=rand()%90;
//  deg+=1.0*(rand()%100000)/100000.0;
    while(t--)
    {
        ans=10000000000;
        n=read();
        for(int i=1;i<=2*n;i++)
        {
            tx=read(),ty=read();
            a[i].x=tx;
            a[i].y=ty;
            if(i<=n)a[i].t=1;
            else a[i].t=2;
        }
        sort(a+1,a+2*n+1,cmp);
        for(int i=1;i<=2*n;i++)
            for(int j=1;j<=500&&(i+j)<=2*n;j++)
                if(a[i].t!=a[i+j].t)
                    ans=min(ans,dis(a[i],a[i+j]));
        cout<<fixed<<setprecision(3)<<ans<<'\n';        
    }
    return 0;
}

AC link