LA 2963 Hypertransmission -

题目地址：http://vjudge.net/problem/UVALive-2963

目标：不稳定的星球越多越好，其次才是R越小越好

最简单的就是直接暴力，枚举所有R（任意两点之间的距离），计算在此R内不稳定的星球的数量：枚举每个点，他们在R长度内，到其他星球A和B的数量

但是这样子有n*m*m复杂度。想想有什么能改进的

因为R肯定是某任意两点之间的距离，将其从小到达枚举的，那么在算第二个R时，第一个算过的又算了一遍，那么可以想 ，保存Ri的点的A和B值，算Ri+1的点的A和B值只要找出边长大于Ri且小于Ri+1的点就好

或者更加简单点，对于比R长的边肯定没用了，所以可以看作没有，只关心小于等于R的边，用一个数组temp[i]保存在此时图(所有边长在R内)中对于i点和它相同的点的点的数量减去不同点的数量，然后从小到大枚举R(加边)，如R内（u，v），如果pu!=pv那么temp[u]++,temp[v]++, 否则都--，且此时图是在R=dist(u,v) 的条件下，那么可以更新答案了

这样子只要扫描所有的边就好了

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b)  for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
const int maxn=1000+5;
struct Point
{int x,y,z,p;
}points[maxn];
struct Edge
{int from,to,dist;bool operator < (const Edge& e) const {return dist<e.dist;}
};
vector<Edge> edges;
int temp[maxn];
int main(int argc, char const *argv[])
{int n;while(scanf("%d",&n)==1&&n){REP(i,1,n){ temp[i]=1;scanf("%d%d%d%d",&points[i].x,&points[i].y,&points[i].z,&points[i].p);}edges.clear();REP(i,1,n) REP(j,i+1,n) {int d=(points[i].x-points[j].x)*(points[i].x-points[j].x)+(points[i].y-points[j].y)*(points[i].y-points[j].y)+(points[i].z-points[j].z)*(points[i].z-points[j].z);edges.push_back(Edge{i,j,d});}sort(edges.begin(), edges.end());int cnt=0,MinR=0,MaxP=0,i=0;while(i<(int)edges.size()){int j=i;while(j<(int)edges.size()&&edges[j].dist==edges[i].dist){int u=edges[j].from,v=edges[j].to;if(points[u].p^points[v].p) {if(--temp[u]==-1) cnt++;if(--temp[v]==-1) cnt++;}else {if(++temp[u]==0) cnt--;if(++temp[v]==0) cnt--;}j++;}if(cnt>MaxP) MaxP=cnt,MinR=edges[i].dist;i=j;}printf("%d\n%.4lf\n", MaxP,sqrt(MinR));}return 0;
}