地图上标注了 n 个野人居住的地点(可以看作是平面上的坐标)。
我们知道,同一个部落的野人总是生活在附近。我们把两个部落的距离,定义为部落中距离最近的那两个居住点的距离。
聪聪知道这些野人总共被分为了 K个部落。
对于任意一种部落划分的方法,都能够求出两个部落之间的距离,求一种部落划分的方法,使最近的两个部落尽可能远。
二分这个最近的距离, 看能否组成K个部落
#include <iostream> #include <cstring> #include <cmath> #include <algorithm> #include <iomanip> using namespace std ; const double E=1e-4; const int N=2e4; double x[N],y[N]; int n,m,fa[N]; double dist(int i,int j){ return (x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]); } int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); } void cmb(int x,int y){ fa[find(x)]=find(y); } int chk(double md){ int i,j,ct=0; for(i=1;i<=n;i++) fa[i]=i; for(i=1;i<=n;i++) for(j=1;j<=n;j++){ if(dist(i,j)<=md) cmb(i,j); } for(i=1;i<=n;i++) if(i==find(i)) ct++; return ct>=m; } signed main(){ int i; double l=0.0,r=1e6, mx,my; cin>>n>>m; for(i=1;i<=n;i++) cin>>x[i]>>y[i], mx=mx>x[i]?mx:x[i]; my=my>y[i]?my:y[i];; r=mx*mx+my*my; while(r-l>E){ double md=(l+r)/2; if(chk(md)) l=md; else r=md; } printf("%.2lf",sqrt(l)); }
标签:JSOI2010,部落,int,double,P4047,include,my,mx From: https://www.cnblogs.com/towboa/p/17208640.html