记录编号	44448	评测结果	AAAAAATTTT
题目名称	[顾研NOIP] 超空间电台	最终得分	60
用户昵称	Makazeu	是否通过	未通过
代码语言	C++	运行时间	4.160 s
提交时间	2012-10-18 20:00:27	内存使用	7.87 MiB

#include <cstdio>
#include <cstdlib>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN=555;
class Star{public:double x,y,z;int stype;}S[MAXN];
set<double> hash;int N;
class Stardist{public:double dist;int stype;};
class Starpoint
{
public:
	Stardist pdist[MAXN];
	int starnum[MAXN];
}Ad[MAXN];

bool cmp(const Stardist&a,const Stardist&b) 
{
	return a.dist<b.dist;
}
inline double sqr(double a) 
{
	return a*a;
}
inline void init()
{
	for(int i=1;i<=N;i++)
		scanf("%lf %lf %lf %d",&S[i].x,&S[i].y,&S[i].z,&S[i].stype);
	double dist;
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=N;j++)
		{
			dist=sqr(S[j].x-S[i].x)+sqr(S[j].y-S[i].y)+sqr(S[j].z-S[i].z);
			Ad[i].pdist[j].dist=dist;
			Ad[i].pdist[j].stype=S[j].stype;
			hash.insert(dist);
		}
		sort(Ad[i].pdist+1,Ad[i].pdist+1+N,cmp);
		Ad[i].starnum[0]=0;
		for(int j=1;j<=N;j++)
		{
			Ad[i].starnum[j]=0;
			if(Ad[i].pdist[j].stype==S[i].stype) 
				Ad[i].starnum[j]=Ad[i].starnum[j-1]+1;
			else Ad[i].starnum[j]=Ad[i].starnum[j-1];
		}
	}
}

inline int binarychop(int k,double dist)
{
	int l=0,r=N,mid,res;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(Ad[k].pdist[mid].dist<=dist) {res=mid;l=mid+1;continue;}
		r=mid-1; continue;
	}
	return res;
}

inline void work()
{
	set<double> :: iterator iter; double nowdist;
	int nownum; int MaxNum=0;double MaxDist;
	for(iter=hash.begin();iter!=hash.end();iter++)
	{
		nowdist=*iter; nownum=0;
		int fugai,have;
		for(int i=1;i<=N;i++)
		{
			fugai=binarychop(i,nowdist);
			have=Ad[i].starnum[fugai];
			if(have*2>=fugai) continue;
			nownum++;
		}
		if(nownum>MaxNum)
		{
			MaxNum=nownum;
			MaxDist=nowdist;
		}
	}
	printf("%d\n%.4lf\n",MaxNum,sqrt(MaxDist));
}

int main(int argc, char const *argv[])
{
	freopen("hyper.in","r",stdin);
	freopen("hyper.out","w",stdout);
	scanf("%d\n",&N);
	init();
	work();
	return 0;
}