题意：空间中有n个整点（1<=n<=1000），点分为两类，如果以某点为球心，R为半径，球面及球内与它不同类的点多于与它同类的点，那么称该点是不稳定的。同类点包括自己。问至多有多少个点是不稳定的，不稳定点最多时R的最小值是多少。
根据数据范围，我们需要一个 O(n2) 的算法。刘汝佳老师说这是扫描法……怎么扫描呢？把问题简化到二维，发现仍不会做。简化到一维，还是不会做……不过一维情形下借助扫描法我会求R=r时不稳定的点的个数。二分？不具备单调性。枚举？枚举所有可行的距离？就算会计算三维情形下给定半径不稳定点的数目， O(n3) 也不可行啊……
瞥了一眼题解，第一步是枚举所有点对及两点间距离。
好像可行的样子QAQ 按距离排个序，维护每个点和多少个同类点距离不大于r、和多少个异类点距离不大于r。两者大小关系变化且r将要发生变化时更新答案。
一开始没注意r将要发生变化时才更新答案，也没仔细看原题题面，没注意自己和自己同类。
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX_N = 1000;
int v[MAX_N];
bool f[MAX_N];struct Point {int x, y, z, p;
} P[MAX_N];
struct Pair {int a, b;double r;bool operator<(const Pair& rhs) const{return r < rhs.r;}
} S[MAX_N*(MAX_N-1)/2+1];inline double sq(double x)
{return x*x;
}inline double dist(Point& a, Point& b)
{return sqrt(sq(a.x-b.x) + sq(a.y-b.y) + sq(a.z-b.z));
}int main()
{int n;scanf("%d", &n);int m = n*(n-1)/2;for (int i = 0; i < n; ++i) {scanf("%d %d %d %d", &P[i].x, &P[i].y, &P[i].z, &P[i].p);v[i] = 1;}for (int i = 0, t = 0; i < n; ++i)for (int j = i+1; j < n; ++j)S[t++] = (Pair){i, j, dist(P[i], P[j])};sort(S, S+m);S[m].r = -1;int d = 0, cnt = 0;double r = 0;for (int i = 0; i < m; ++i) {Pair& now = S[i];int a = now.a, b = now.b;if (P[a].p == P[b].p)++v[a], ++v[b];else--v[a], --v[b];// v[x] < 0 <=> f[x] = trueif (v[a] < 0 && !f[a])++cnt, f[a] = true;if (v[a] >= 0 && f[a])--cnt, f[a] = false;if (v[b] < 0 && !f[b])++cnt, f[b] = true;if (v[b] >= 0 && f[b])--cnt, f[b] = false;if (now.r != S[i+1].r && cnt > d) {d = cnt;r = S[i].r;}}printf("%d\n%.4f\n", d, r);return 0;
}