CF333E Summer Earnings 题解

学到了bitset优化。

三个圆可以相切或相离，即任意两点间距离大于圆的直径。以下将三点间图形视作三角形。

先考虑暴力，我们先求出这些点两两之间的距离作为边，然后从大到小枚举这些边作为三角形中最短的一条边并加入图中，再枚举两个端点所连边，如果两个点有一个连边的公共点，那一定可行，且此处枚举的边即为最大值。

考虑优化，复杂度可以到$O(n^2)$，边的枚举无法优化，优化查找公共点过程，使用bitset作为邻接矩阵，用&运算代替枚举，复杂度为$O(n^3/w)$，可过。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define LD long double
const LL MAXN=3005;
LL n;
struct node{
    LL u,v;
    LD w;
    bool operator <(const node &t)const{
        return w>t.w;
    }
}e[5000005];
LL x[MAXN],y[MAXN],cnt;
bitset<MAXN>b[MAXN];
LD cal(LL a,LL b){
return sqrtl(1.0l*(x[a]-x[b])*(x[a]-x[b])+1.0l*(y[a]-y[b])*(y[a]-y[b]));
}
int main(){
    scanf("%lld",&n);
    for(LL i=1;i<=n;i++){
        scanf("%lld%lld",&x[i],&y[i]);
        for(LL j=1;j<i;j++){
            e[++cnt].u=i;e[cnt].v=j;
            e[cnt].w=cal(i,j);
        }
    }
    sort(e+1,e+cnt+1);
    for(LL i=1;i<=cnt;i++){
        b[e[i].u][e[i].v]=1;
b[e[i].v][e[i].u]=1;
if((b[e[i].u]&b[e[i].v]).count()){
printf("%.10Lf",e[i].w/2.0l);
return 0; 
}
    }
    printf("0");
}

原文地址：https://blog.csdn.net/WANG_ZIYE/article/details/142496988

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！