题目链接：UVA1325

【题意】要在n个星球上各装一个广播装置，作用范围均为R（即和它距离不超过R的星球能收听到它的广播）。每个星球广播A类节目或者B类节目。另N+（i）表示星球i能收听到的和自己广播相同节目的星球数量（包括星球i自己），N-（i）表示星球i收听到广播另一种节目的星球数。如果N+（i）<N-（i），我们就说星球i是不稳定的。你是暗黑世界的间谍，因此希望选择R，使得不稳定的星球尽量多。在此前提下，R应尽量小。

【分析】需要用扫描的思想，直接暴力肯定超时的，首先可以知道最大不稳定的星球数量肯定在r的值为某两个星球的距离，这样先枚举出所有星球之间的距离，这样已经是O(N^2)复杂度了，对于1000的N来说基本上只能线性扫描了；还可以发现只要把距离从小到大排序，以前小的距离计算过的每个星球的稳定值na(就是[n+(i)] – [n-(i)]的值)可以被大的距离所利用，每次改变的na其实只是距离为当前r的所有两两对应的星球，这样只要两个星球为同一频段那就把两个星球的na都+1，反之-1，这样每次当-++na == 0时说明这个星球刚好从不稳定变成稳定，–na==-1时改星球从稳定变成不稳定；最后需要注意把所有距离相等的要都算完后再更新ans，还有所有星球都是同一频段的时候r为0、

【AC CODE】343ms

 

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 1000 + 10;
struct NODE{
	int x, y, z, type;
}p[MAXN];
struct S{
	int u, v, dis;
	bool operator<(const S&t)const{
		return dis < t.dis;
	}
}s[MAXN*MAXN];
int na[MAXN];//na+和na-的差,na<0时表示星球不稳定

inline int get_dis(int a, int b)
{
	return (p[a].x - p[b].x)*(p[a].x - p[b].x) + (p[a].y - p[b].y)*(p[a].y - p[b].y) + (p[a].z - p[b].z)*(p[a].z - p[b].z);
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int n;
	while (~scanf("%d%*c", &n))
	{
		rep(i, 0, n) scanf("%d %d %d %d%*c", &p[i].x, &p[i].y, &p[i].z, &p[i].type);
		int cnt = 0;
		rep(i, 0, n)
		{
			na[i] = 1;
			rep(j, i + 1, n)
				s[cnt++] = { i, j, get_dis(i, j) };
		}
		sort(s, s + cnt);
		int ans = 0, tmp = 0, r = 0;
		rep(i, 0, cnt)
		{
			int u = s[i].u, v = s[i].v;
			if (p[u].type == p[v].type)
			{
				if (++na[u] == 0) tmp--;
				if (++na[v] == 0) tmp--;
			}
			else
			{
				if (--na[u] == -1) tmp++;
				if (--na[v] == -1) tmp++;
			}
			if (i != cnt - 1 && s[i].dis == s[i + 1].dis) continue;
			if (tmp > ans)
			{
				ans = tmp;
				r = s[i].dis;
			}
		}
		printf("%d\n%.4f\n", ans, sqrt((double)r));
	}
	return 0;
}