P4357

发表于 分类于
[CQOI2016]K 远点对

[CQOI2016]K 远点对

这个题 $k$ 比较小，实话说第一眼看到我也在想凸包应该怎么做。

正确的做法是先旋转卡壳卡出最远点，然后把所有点与这两个点的距离丢进小根堆，再删去这个点，重复以上过程 $k$ 次，并维护堆的大小为 $k$，最后的堆顶就是答案。

这个应该很好理解，时间复杂度 $O(nk\log k)$ 的。

有时间我把板子粘过来做一下（咕咕咕咕）。

K-D 树的做法是划分完二维平面后，枚举一个点，在 K-D 树上查询与其距离较远的点，并用一个小根堆维护这些距离，维护这个小根堆的大小为 $2k$（点对统计两次），遇到更大的解往里面塞就可以了。

剪枝的话就是点集与该点最远距离都塞不到小根堆里，剪掉就好。

最后玄学过掉。

最坏的时间复杂度是 $O(n^2\log k)$ 的。

代码（K-D 树）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#define ll long long
#define ld long double
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;

const ll N=1e5;

ll n,k;
ll lc[N+5],rc[N+5],L[N+5],R[N+5],D[N+5],U[N+5];
priority_queue<ll,vector<ll>,greater<ll> > q;

struct node{ll x,y;}a[N+5];

inline bool Cmp1(node a,node b) {return a.x<b.x;}
inline bool Cmp2(node a,node b) {return a.y<b.y;}

inline void Maintain(ll x) {
  L[x]=R[x]=a[x].x;D[x]=U[x]=a[x].y;
  if(lc[x]) {
    L[x]=min(L[x],L[lc[x]]);R[x]=max(R[x],R[lc[x]]);
    D[x]=min(D[x],D[lc[x]]);U[x]=max(U[x],U[lc[x]]);
  }
  if(rc[x]) {
    L[x]=min(L[x],L[rc[x]]);R[x]=max(R[x],R[rc[x]]);
    D[x]=min(D[x],D[rc[x]]);U[x]=max(U[x],U[rc[x]]);
  }
}

inline ll Build(ll l,ll r) {
  if(l>r) return 0;ll mid=(l+r)>>1;
  ld av1=0,av2=0,va1=0,va2=0; // Average & Variance.
  for(ll i=l;i<=r;i++) {av1+=a[i].x;av2+=a[i].y;}
  av1/=(ld)(r-l+1);av2/=(ld)(r-l+1);
  for(ll i=l;i<=r;i++) {
    va1+=(av1-a[i].x)*(av1-a[i].x);va2+=(av2-a[i].y)*(av2-a[i].y);
  }
  if(va1>va2) {nth_element(a+l,a+mid,a+r+1,Cmp1);}
  else {nth_element(a+l,a+mid,a+r+1,Cmp2);}
  lc[mid]=Build(l,mid-1);rc[mid]=Build(mid+1,r);
  Maintain(mid);return mid;
}

inline ll Sqr(ll x) {return x*x;}
inline ll Dist(ll u,ll v) {
  return max(Sqr(a[u].x-L[v]),Sqr(a[u].x-R[v]))
  +max(Sqr(a[u].y-D[v]),Sqr(a[u].y-U[v]));
}

inline void Query(ll l,ll r,ll x) {
  if(l>r) return;ll mid=(l+r)>>1;
  ll t=Sqr(a[mid].x-a[x].x)+Sqr(a[mid].y-a[x].y);
  if(t>q.top()) {q.pop();q.push(t);}
  ll distl=Dist(x,lc[mid]),distr=Dist(x,rc[mid]);
  if(distl>q.top()&&distr>q.top()) {
    if(distl>distr) {Query(l,mid-1,x);if(distr>q.top()) Query(mid+1,r,x);}
    else {Query(mid+1,r,x);if(distl>q.top()) Query(l,mid-1,x);}
  }
  else {
    if(distl>q.top()) Query(l,mid-1,x);
    if(distr>q.top()) Query(mid+1,r,x);
  }
}

int main() {

  n=read();k=read();k<<=1;
  for(ll i=1;i<=k;i++) q.push(0);
  for(ll i=1;i<=n;i++) {a[i].x=read();a[i].y=read();}
  
  Build(1,n);
  for(ll i=1;i<=n;i++) Query(1,n,i);

  write(q.top());

  return 0;
}