https://vjudge.net/problem/UVALive-2963
题意：
需要在n个星球上各装一个广播装置，作用范围均为R。每个星球广播A类节目或者B类节目。a表示星球i收听到的和自己广播相同节目的星球数（包括星球i自己），b表示不想同，如果a<b，说明星球是不稳定的，现在要选择尽量小的R，使得不稳定的星球尽量多些。
思路：
先把所有点之间的距离计算出来并排好序。
接下来我们就按照边长来依次扫描，每次根据扫描的信息动态维护每个星球的稳定情况。
需要注意的是处理好边长相同的情况。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL;
typedef pair<int,int> pll;
const int INF=0x3f3f3f3f;
const int maxn=+; int n;
int num[maxn]; struct Point
{
int x,y,z,p;
}a[maxn]; struct Edge
{
int x,y;
double d;
bool operator<(const Edge& rhs) const
{
return d<rhs.d;
}
}e[maxn*maxn]; double cacl(int i,int j)
{
int x=a[i].x-a[j].x,y=a[i].y-a[j].y,z=a[i].z-a[j].z;
return sqrt((double)x*x+(double)y*y+(double)z*z);
} int main()
{
//freopen("D:\\input.txt","r",stdin);
while(~scanf("%d",&n))
{
for(int i=;i<=n;i++)
{
scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].z,&a[i].p);
num[i]=;
} int cnt=;
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
{
e[cnt].x=i;
e[cnt].y=j;
e[cnt].d=cacl(i,j);
cnt++;
} int temp=;
int ans=;
double length=;
sort(e,e+cnt);
for(int i=;i<cnt;i++)
{
int u=e[i].x,v=e[i].y;
if(a[u].p!=a[v].p)
{
num[u]--;
num[v]--;
if(num[u]==-) temp++; //如果=-1，则由稳定变成了不稳定
if(num[v]==-) temp++;
}
else
{
num[u]++;
num[v]++;
if(num[u]==) temp--;
if(num[v]==) temp--;
} if(i!=cnt- && e[i].d==e[i+].d) continue; //处理距离相等的边
if(ans<temp)
{
ans=temp;
length=e[i].d;
}
}
printf("%d\n%.4f\n",ans,length);
}
return ;
}