本文共 2944 字，大约阅读时间需要 9 分钟。
80分打法
首先二分最后答案，答案即为r，可看作以每个k为圆心r为半径的圆
我们进行并查集维护，维护相交的圆的边界
最后判断是否存在圆将上下边界覆盖，如有证明不行
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #define min(a,b) a>b?b:a11 #define max(a,b) a>b?a:b12 #define int long long 13 #define MAXN 100000114 using namespace std;15 int fa[MAXN];16 double l_y[MAXN],r_y[MAXN];17 int x[MAXN],y[MAXN];18 int find(int x)19 {20 if(fa[x]==x)return fa[x];21 return fa[x]=find(fa[x]);22 }23 bool judge(int xx,int yy,double r)24 {25 double deta_x=abs(x[xx]-x[yy]);26 double deta_y=abs(y[xx]-y[yy]);27 //printf("deta_x=%lld deta_y=%lld\n",deta_x,deta_y);28 if((double)deta_x*deta_x+(double)deta_y*deta_y<(2.0*r)*(r*2.0))return 1;29 return 0;30 }31 int n,m,k;32 bool work(double cir)33 {34 for(int i=1;i<=k;++i)fa[i]=i;35 for(int i=1;i<=k;++i)36 {37 l_y[i]=(double)y[i]-cir;r_y[i]=(double)y[i]+cir;38 }39 for(int i=1;i<=k;++i)40 {41 for(int j=1;j<=k;++j)42 {43 //printf("i=%lld j=%lld\n",i,j);44 int xx=find(i);int yy=find(j);45 if(xx==yy)continue;46 if(judge(i,j,cir))47 {48 fa[yy]=xx;49 l_y[yy]=l_y[xx]=min(l_y[yy],l_y[xx]);50 r_y[yy]=r_y[xx]=max(r_y[yy],r_y[xx]); 51 //printf("l_y[%lld]=%.4lf r_y[%lld]=%.4lf\n",xx,l_y[xx],xx,r_y[xx]); 52 }53 }54 }55 for(int i=1;i<=k;++i)56 {57 if(l_y[find(i)] m-cir)58 {59 //printf("l_y[%lld]=%.4lf r_y[%lld]=%.4lf\n",find(i),l_y[find(i)],find(i),r_y[find(i)]); 60 return 0;61 }62 }63 return 1;64 }65 void second_divided()66 {67 double l=0.0,r=m;68 while(l+0.0000001
100分
开始是很难看出这是最小生成树，（听说是什么欧几里得最小生成树，非常神奇）
对于最小生成树有几个性质：（自己瞎写的，可能不对）
1.最小生成树包含两点之间路径的最小边
2.最小生成树生成的边和最小
对于此题，我们尽量选边权小的边，构成最小生成树，
选出从上边界到下边界的最大边权，除二既是答案
最小生成树保证了选出这个边后，其他圆只会离他更远，所以正确
另外学习了
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #define min(a,b) a>b?b:a11 #define max(a,b) a>b?a:b12 #define int long long 13 #define MAXN 100000114 using namespace std;15 double disx[MAXN],disy[MAXN];16 int n,m,k;17 double d[MAXN];int vis[MAXN];int fa[MAXN];18 double poww(double x)19 {20 return x*x;21 }22 struct no{ int to,n;double w;}e[MAXN*2];int head[MAXN],tot;23 void add(int u,int v,double w)24 {25 e[++tot].to=v;e[tot].n=head[u];e[tot].w=w;head[u]=tot;26 }27 double cal(int x,int y)28 {29 if(x>y)swap(x,y);30 if(x==k+1&&y==k+2)return (double)m;31 if(y==k+1)return disy[x];32 if(y==k+2)return (double)m-disy[x];33 //printf("cal%.4lf\n",sqrt(poww(disx[x]-disx[y])+poww(disy[x]-disy[y])));34 return sqrt(poww(disx[x]-disx[y])+poww(disy[x]-disy[y]));35 }36 void prim()37 {38 memset(vis,0,sizeof(vis));39 for(int i=1;i<=k+2;++i)d[i]=100000000000.0;40 d[1]=0;41 for(int i=1;i
转载于:https://www.cnblogs.com/Wwb123/p/11370472.html
