题意：需要在n个星球上各安装广播器，范围为R，每个星球是A节目或者B节目，令N+（i）表示范围内与自己相同节目的个数(包括自己)，N-（i）表示不想同的个数，如果
N+(i) < N-(i)表示星球i是不稳定的，选择R，使得不稳定的星球尽量多，在此前提下，R尽量小
思路：先预处理出任意两个星球的距离，然后排序，R一定是这些距离中的一个，从小开始枚举，同种距离的一起处理，不断的更新信息求出最大值
#include#include #include #include #include using namespace std; const int MAXN = 1010; struct node{ int x,y,z; int type; }p[MAXN]; int n; struct Node{ int s,t; int dist; bool operator<(const Node &r)const{ return dist < r.dist; } }q[MAXN*MAXN/2]; int val[MAXN]; int dis(node a,node b){ return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z); } int main(){ while (scanf("%d",&n) != EOF){ for (int i = 0; i < n; i++) scanf("%d%d%d%d",&p[i].x,&p[i].y,&p[i].z,&p[i].type); int cnt = 0; for (int i = 0; i < n; i++){ val[i] = 1; for (int j = i+1; j < n; j++){ q[cnt].s = i; q[cnt].t = j; q[cnt].dist = dis(p[i],p[j]); cnt++; } } sort(q,q+cnt); int temp,ans,d; temp = ans = d = 0; int i,j; for (i = 0; i < cnt;){ for (j = i; j < cnt && q[j].dist == q[i].dist; j++){ if (p[q[j].s].type != p[q[j].t].type){ if (--val[q[j].s] == -1) temp++; if (--val[q[j].t] == -1) temp++; } else { if (++val[q[j].s] == 0) temp--; if (++val[q[j].t] == 0) temp--; } } if (temp > ans){ ans = temp; d = q[i].dist; } i = j; } printf("%d\n%.4lf\n",ans,sqrt(d*1.0)); } return 0; }