题解 | E. Summer Earnings

#include<cmath>
#include<algorithm>
#include<iostream>
#include<bitset>
#include<cstdio>
using namespace std;
bitset<4000> a[4000];
struct line{
    int m,n;
    int len2;
}b[3000*3000];
int x[4000];
int y[4000];
bool comp(line a, line b)
{
    return a.len2>b.len2;
}
double dist(int i,int j)
{
    return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
    }
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            b[cnt].m=i;
            b[cnt].n=j;
            b[cnt++].len2 = dist(i,j);
        }
    }
    sort(b,b+cnt,comp);
    for(int i=0;i<cnt;i++)
    {
        if((a[b[i].m]&a[b[i].n])!=0)
        {
            printf("%lf",sqrt(b[i].len2)/2.0);
            break;
        }
        else
        {
            a[b[i].m][b[i].n] = 1;
            a[b[i].n][b[i].m] = 1;
        }
    }
    return 0;
}