学到了bitset优化。
三个圆可以相切或相离，即任意两点间距离大于圆的直径。以下将三点间图形视作三角形。
先考虑暴力，我们先求出这些点两两之间的距离作为边，然后从大到小枚举这些边作为三角形中最短的一条边并加入图中，再枚举两个端点所连边，如果两个点有一个连边的公共点，那一定可行，且此处枚举的边即为最大值。
考虑优化，复杂度可以到$O(n^2)$，边的枚举无法优化，优化查找公共点过程，使用bitset作为邻接矩阵，用&运算代替枚举，复杂度为$O(n^3/w)$，可过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#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");
}
|