【BZOJ1821】[JSOI2010]部落划分(二分,并查集)
二分 划分 查集
2023-09-11 14:14:40 时间
【BZOJ1821】[JSOI2010]部落划分(二分,并查集)
题面
题解
二分答案,把距离小于二分值的点全部并起来,\(\mbox{check}\)一下是否有超过\(K\)个集合就好了。
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define MAX 1010
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int f[MAX],x[MAX],y[MAX],n,K;
double Sqr(double x){return x*x;}
double Dis(int i,int j){return sqrt(Sqr(x[i]-x[j])+Sqr(y[i]-y[j]));}
int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}
bool check(double mid)
{
for(int i=1;i<=n;++i)f[i]=i;
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
if(Dis(i,j)<=mid)f[getf(j)]=getf(i);
int tot=0;
for(int i=1;i<=n;++i)if(i==getf(i))++tot;
return tot>=K;
}
int main()
{
n=read();K=read();
for(int i=1;i<=n;++i)x[i]=read(),y[i]=read();
double l=0,r=2e4;
while(r-l>1e-4)
{
double mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
printf("%.2lf\n",l);
return 0;
}
相关文章
- 【C/C++学院】0723-32位与64位/调戏窗口程序/数据分离算法/内存检索/二分查找法/myVC
- Java实现 LeetCode 719 找出第 k 小的距离对(二分搜索法+二分猜数字)
- 重新整理数据结构与算法—— 二分查找法[十二]
- 【Codeforces Round #422 (Div. 2) C】Hacker, pack your bags!(二分写法)
- 【二分查找】查找算法之二分查找(Binary Search)
- Python每日一练——第8天:二分查找算法
- 二分查找:一种效率较高的查找方法
- 寻找右区间-c语言快速排序加二分查找
- java两种实现二分查找方式
- BZOJ 1305 CQOI2009 dance跳舞 二分答案+最大流
- 一起talk C栗子吧(第二十五回:C语言实例--二分查找)
- 二分查找——Find Peak Element,主要是利用index+1和index-1来判断走向
- 两个有序数组的中位数(第k大的数)——使用二分答案的思路写起来更直观
- 01-复杂度3 二分查找