JZOJ 4353 Distance

首先考虑 ci∈{1,2} 的情况。
可以将一种颜色的点全部插入 K-D Tree，然后枚举另一种颜色的点，在 K-D Tree 上找和它距离最远的点。

直接 O(n) 搜显然炸裂，考虑剪枝：
通过维护子树内点每一维坐标的上下值可以得到一个最小的能覆盖整个子树的矩形，如若这个矩形的四个顶点到查询点的距离的最大值不超过当前答案，就可以退了（
以及查询左右子树时，可以启发式地选择距离更大的那边。
然而复杂度其实也是错的，但它能过（

多种颜色的，可以考虑对颜色分治。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 25e4;
int n,a[N + 5],rt,L[N + 5],R[N + 5];
int ind[N + 5],len;
inline long long dis(int x1,int y1,int x2,int y2)
{
    return (long long)(x1 - x2) * (x1 - x2) + (long long)(y1 - y2) * (y1 - y2);
}
struct node
{
    int x,y,c,dim;
    int L,R,D,U;
    int ls,rs;
    inline bool operator<(const node &o) const
    {
        return c < o.c;
    }
    inline long long maxdis(int x0,int y0) const
    {
        return max(dis(L,D,x0,y0),max(dis(L,U,x0,y0),max(dis(R,D,x0,y0),dis(R,U,x0,y0))));
    }
} kdt[N + 5];
inline bool cmp1(int x,int y)
{
    return kdt[x].x < kdt[y].x;
}
inline bool cmp2(int x,int y)
{
    return kdt[x].y < kdt[y].y;
}
inline void up(int p)
{
    kdt[p].L = kdt[p].R = kdt[p].x,
    kdt[p].D = kdt[p].U = kdt[p].y;
    if(kdt[p].ls)
        kdt[p].L = min(kdt[p].L,kdt[kdt[p].ls].L),kdt[p].R = max(kdt[p].R,kdt[kdt[p].ls].R),
        kdt[p].D = min(kdt[p].D,kdt[kdt[p].ls].D),kdt[p].U = max(kdt[p].U,kdt[kdt[p].ls].U);
    if(kdt[p].rs)
        kdt[p].L = min(kdt[p].L,kdt[kdt[p].rs].L),kdt[p].R = max(kdt[p].R,kdt[kdt[p].rs].R),
        kdt[p].D = min(kdt[p].D,kdt[kdt[p].rs].D),kdt[p].U = max(kdt[p].U,kdt[kdt[p].rs].U);
}
int build(int l,int r)
{
    if(l > r)
        return 0;
    int mid = l + r >> 1;
    double av1 = 0,av2 = 0,v1 = 0,v2 = 0;
    for(register int i = l;i <= r;++i)
        av1 += kdt[a[i]].x,av2 += kdt[a[i]].y;
    av1 /= r - l + 1,av2 /= r - l + 1;
    for(register int i = l;i <= r;++i)
        v1 += (kdt[a[i]].x - av1) * (kdt[a[i]].x - av1),
        v2 += (kdt[a[i]].y - av2) * (kdt[a[i]].y - av2);
    if(v1 > v2)
        nth_element(a + l,a + mid,a + r + 1,cmp1),kdt[a[mid]].dim = 1;
    else
        nth_element(a + l,a + mid,a + r + 1,cmp2),kdt[a[mid]].dim = 2;
    kdt[a[mid]].ls = build(l,mid - 1),kdt[a[mid]].rs = build(mid + 1,r);
    up(a[mid]);
    return a[mid];
}
long long ans;
void query(int p,int x,int y)
{
    if(!p || kdt[p].maxdis(x,y) <= ans)
        return ;
    ans = max(ans,dis(kdt[p].x,kdt[p].y,x,y));
    if(kdt[kdt[p].ls].maxdis(x,y) > kdt[kdt[p].rs].maxdis(x,y))
        query(kdt[p].ls,x,y),query(kdt[p].rs,x,y);
    else
        query(kdt[p].rs,x,y),query(kdt[p].ls,x,y);
}
void solve(int lc,int rc)
{
    if(lc == rc)
        return ;
    int mid = lc + rc >> 1;
    for(register int i = L[mid + 1];i <= R[rc];++i)
        a[i] = i;
    rt = build(L[mid + 1],R[rc]);
    for(register int i = L[lc];i <= R[mid];++i)
        query(rt,kdt[i].x,kdt[i].y);
    solve(lc,mid),solve(mid + 1,rc);
}
int main()
{
    scanf("%d",&n);
    for(register int i = 1;i <= n;++i)
        scanf("%d%d%d",&kdt[i].x,&kdt[i].y,&kdt[i].c),ind[i] = kdt[i].c;
    sort(ind + 1,ind + n + 1),len = unique(ind + 1,ind + n + 1) - ind - 1;
    for(register int i = 1;i <= n;++i)
        kdt[i].c = lower_bound(ind + 1,ind + len + 1,kdt[i].c) - ind;
    sort(kdt + 1,kdt + n + 1);
    for(register int i = 1;i <= n;++i)
        !L[kdt[i].c] && (L[kdt[i].c] = i),R[kdt[i].c] = i;
    solve(1,len);
    printf("%lld\n",ans);
}