比赛 |
顾研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;
}