怎么说呢，只能说自己还不够熟练，能力还不够，细心成都还不够吧。这样的二分题目在POJ的训练计划里面有类似的题目，自己也是都刷了，可是在调这道题目的时候废了老大的尽了，比赛结束后听polla的一句<t才属于同一类，才知道自己怎么犯了这么二逼的错误呢！唉。。。。自己给弄成>t了。改过后终于出来了。
思路：找出最大的t，如果按t分类，可分出1组，按0分类分出n组，二分枚举t然后利用并查集判断分出多少种类。
#include#include #include #define maxn 1007using namespace std;const double eps = 1e-8;int n,m,k;double t;int f[maxn];struct node{ double x,y,z;}p[maxn];int cmp(double x){ if (x > eps) return 1; else if (x < -eps) return -1; else return 0;}int find(int x){ if (x != f[x]) f[x] = find(f[x]); return f[x];}void Union(int x,int y){ x = find(x); y = find(y); if (x != y) f[y] = x;}double getse(int a,int b){ double x = p[b].x - p[a].x; double y = p[b].y - p[a].y; double z = p[b].z - p[a].z; return (x*x + y*y + z*z);}//并查集判断是否属于同一类int getnum(double tx){ int i,j; for (i = 0; i < n; ++i) f[i] = i; for (i = 0; i < n; ++i) { for (j = i + 1; j < n; ++j) { double tmp = getse(i,j); if (cmp(tmp - tx) < 0) //就是这里的二逼错误让我调了很长时间 Union(i,j); } } int ct = 0; for (i = 0; i < n; ++i) { if (i == find(i)) ct++; } return ct;}int main(){ int i,j; t = 0; scanf("%d%d",&n,&k); for (i = 0; i < n; ++i) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z); double pt; for (i = 0; i < n; ++i) { for (j = 0; j < n; ++j) { if (i != j) { pt = getse(i,j); if (pt > t) t = pt; } } } //printf("%lf\n",t); double l = 0; double r = t; double mid = 0; //二分枚举 while (cmp(l - r) < 0) { mid = (l + r)/2.0; int tt = getnum(mid); //printf(">> %lf %lf %lf %d\n",l,r,mid,tt); if (tt >= k) l = mid; else r = mid; } printf("%.6lf\n",l);}