比赛 顾研NOIP2011模拟赛 评测结果 AAAAAAAAAA
题目名称 超空间电台 最终得分 100
用户昵称 feng 运行时间 2.057 s
代码语言 C++ 内存使用 11.86 MiB
提交时间 2012-10-17 20:57:27
显示代码纯文本
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<iomanip>
using namespace std;
struct node{
	long long d;
	int v;
}f[600][600];
struct typ{
	int x,y,z,v;
}a[600];
long long  w[300000];
int b[300000];
int t[300000];
int p;
int l,r,m;
int o;
node s[600];
int n;
bool cmp(node a,node b){
	return a.d<b.d;
}
int main()
{
	freopen("hyper.in","r",stdin);
	freopen("hyper.out","w",stdout);
	memset(f,0,sizeof(f));
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].z,&a[i].v);
	p=0;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			s[j].d+=(a[i].x-a[j].x)*(a[i].x-a[j].x);
			s[j].d+=(a[i].y-a[j].y)*(a[i].y-a[j].y);
			s[j].d+=(a[i].z-a[j].z)*(a[i].z-a[j].z);
			if (a[i].v==a[j].v) s[j].v=1; else s[j].v=-1;
			w[++p]=s[j].d;
		}
		sort(s+1,s+n+1,cmp);
		for (int j=1;j<=n;j++)
			f[i][j]=s[j];
		memset(s,0,sizeof(s));
	}
	sort(w+1,w+p+1);
	for (int i=1;i<=n;i++){
		int sum=0;
		for (int j=1;j<=n;j++){
			sum+=f[i][j].v;
			if (sum<0){
				f[i][j].v=1;
			}else{
				f[i][j].v=0;
			}
		}
	}
	
	memset(b,-1,sizeof(b));
	memset(t,0,sizeof(t));
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			l=1;r=p;
			m=(l+r)/2;
			while (l<r){
				if (f[i][j].d>w[m]) l=m+1;else r=m;
				m=(l+r)/2;
			}
			b[m]=f[i][j].v;
		}
			int o=0;
			for (int j=1;j<=p;j++){
				if (b[j]>=0)
					o=b[j];
				t[j]+=o;
			}
			memset(b,-1,sizeof(b));
	}
	int maxn=0;
	o=0;
	for (int i=p;i>=1;i--){
		if (t[i]>=maxn){
			maxn=t[i];
			o=i;
		}
	}
	cout<<maxn<<endl;
	double ans=sqrt((double)w[o]);
	cout << fixed << setprecision(4) <<ans<< endl;
	return 0;
}