百度之星 / 初赛第二场 B题

百度之星 / 初赛第二场 B题

怎么说呢，只能说自己还不够熟练，能力还不够，细心成都还不够吧。这样的二分题目在POJ的训练计划里面有类似的题目，自己也是都刷了，可是在调这道题目的时候废了老大的尽了，比赛结束后听polla的一句<t才属于同一类，才知道自己怎么犯了这么二逼的错误呢！唉。。。。自己给弄成>t了。改过后终于出来了。

思路：找出最大的t，如果按t分类，可分出1组，按0分类分出n组，二分枚举t然后利用并查集判断分出多少种类。

#include <cstdio>
#include <cstring>
#include <iostream>
#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("%lfn",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 %dn",l,r,mid,tt);if (tt >= k)  l = mid;else r = mid;}printf("%.6lfn",l);
}

转载于:.html