我 kd tree 过了/jy

听说这题把 kd tree 卡了？

我加了个卡时就过了。请求加强数据。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <random>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double lf;

// #define int ll
#define rep(i, f, t) for (int i = (f), ed##i = (t); i <= ed##i; ++i)
#define re(i, t) rep (i, 1, t)
#define per(i, t, f) for (int i = (t), ed##i = (f); i >= ed##i; --i)
#define ste(i, f, t, s) for (int i = (f), ed##i = (t); i <= ed##i; i += s)
#define each(i, x) for (auto &&i : (x))
#define nxt(i, f, g) for (int i = g.h[f]; i; i = g.e[i].n)
#define dbg(x) (cerr << "\033[34m" << #x " = " << (x) << "\033[0m\n")
#define umod(x) ((x) >= mo && ((x) -= mo))
#define dmod(x) ((x) < 0 && ((x) += mo))
#define up(x, y) (((x) < (y)) && ((x) = (y)))
#define down(x, y) (((x) > (y)) && ((x) = (y)))
#define y1 y1__
#define fio(x) (freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout))
#define sqr(x) (1ll * (x) * (x))

// clang-format off
namespace FastIO {
    const int SZ=(1<<21)+1;
    struct I {
        char ibuf[SZ],*iS,*iT,c;int f,_eof;FILE*fi;
        I(FILE*f):fi(f){}
        inline char Gc(){return iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SZ,fi),(iS==iT?EOF:*iS++)):*iS++;}
        inline ll operator()(){ll x;operator()(x);return x;}
        inline I&operator()(char&x){x=Gc();return*this;}
        inline I&operator()(char*s){for(c=Gc();c<32||c>126||c==' ';)c=Gc();for(;c>31&&c<127&&c!=' '&&c!='\n'&&c!='\r';++s,c=Gc())*s=c;*s=0;return*this;}
        template<class T>inline I&operator()(T&x){_eof=0;for(f=1,c=Gc();(c<'0'||c>'9')&&!_eof;c=Gc()){if(c=='-')f=-1;_eof|=c==EOF;}for(x=0;c<='9'&&c>='0'&&!_eof;c=Gc())x=x*10+(c&15),_eof|=c==EOF;x*=f;return*this;}
        template<class T>I&operator()(T*x,const int&n,const int&st=1){rep(i,st,n){operator()(x[i]);}return*this;}
    } in(stdin);
    struct O {
        char obuf[SZ],*oS=obuf,*oT=oS+SZ-1,qu[55];int f,qr;FILE*fi;
        O(FILE*f):fi(f){}
        ~O(){Flush();}
        inline void Flush(){fwrite(obuf,1,oS-obuf,fi),oS=obuf;}
        inline O&operator()(char x){*oS++=x;if(oS==oT)Flush();return*this;}
        inline O&operator()(char*s){int len=strlen(s);for(f=0;f<len;++f)operator()(s[f]);return*this;}
        inline O&operator()(const char*s){return operator()((char*)s);}
        template<class T>inline O&operator()(T x){if(!x)operator()('0');if(x<0)operator()('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)operator()(qu[qr--]);return*this;}
        template<class T>O&operator()(T*x,const int&n,const char&ed=' ',const int&st=1){rep(i,st,n)operator()(x[i])(ed);return*this;}
    } out(stdout);
}
using FastIO::in;using FastIO::out;
// clang-format on

const int N = 4e6 + 9;
struct P {
  int x, y;
  int id;
} a[N];
inline P Min(P x, P y) { return {min(x.x, y.x), min(x.y, y.y), -1}; }
inline P Max(P x, P y) { return {max(x.x, y.x), max(x.y, y.y), -1}; }
inline bool operator<=(P x, P y) { return x.x <= y.x && x.y <= y.y; }
inline bool Out(P al, P ar, P bl, P br) {
  return ar.x < bl.x || br.x < al.x || ar.y < bl.y || br.y < al.y;
}
inline bool operator==(P x, P y) { return x.x == y.x && x.y == y.y; }
inline bool operator!=(P x, P y) { return !(x.x == y.x); }

ll ans = 2e18;
namespace Tree {
struct Node {
  P l, r;  // 左上右下
} d[N];
void Build(int u, int l, int r, int b) {
  if (l == r) {
    d[u].l = d[u].r = a[l];
    return;
  }
  int mid = (l + r) / 2;
  if (b)
    nth_element(a + l, a + mid, a + r + 1, [](const P &a, const P &b) { return a.x < b.x; });
  else
    nth_element(a + l, a + mid, a + r + 1, [](const P &a, const P &b) { return a.y < b.y; });
  Build(u << 1, l, mid, !b);
  Build(u << 1 | 1, mid + 1, r, !b);
  d[u].l = Min(d[u << 1].l, d[u << 1 | 1].l);
  d[u].r = Max(d[u << 1].r, d[u << 1 | 1].r);
}
ll Dis1(int a, int b) {
  ll ret = 0;
  if (d[b].l.x > ::a[a].x) ret += sqr(d[b].l.x - ::a[a].x);
  if (d[b].r.x < ::a[a].x) ret += sqr(::a[a].x - d[b].r.x);
  if (d[b].l.y > ::a[a].y) ret += sqr(d[b].l.y - ::a[a].y);
  if (d[b].r.y < ::a[a].y) ret += sqr(::a[a].y - d[b].r.y);
  return ret;
}
void Find(int p, int u, int l, int r) {
  if (Dis1(p, u) > ans) return;
  if (l == r) {
    if (a[p].id != d[u].l.id) down(ans, sqr(a[p].x - d[u].l.x) + sqr(a[p].y - d[u].l.y));
    return;
  }
  int mid = (l + r) / 2;
  ll dl = Dis1(p, u << 1), dr = Dis1(p, u << 1 | 1);
  if (dl < dr)
    Find(p, u << 1, l, mid), Find(p, u << 1 | 1, mid + 1, r);
  else
    Find(p, u << 1 | 1, mid + 1, r), Find(p, u << 1, l, mid);
}
}  // namespace Tree

int n;

signed main() {
  in(n);
  re (i, n)
    in(a[i].x)(a[i].y), a[i].id = i;
  Tree::Build(1, 1, n, 0);
  re (i, n) {
    if (1.0 * clock() / CLOCKS_PER_SEC > 0.34) break;
    Tree::Find(i, 1, 1, n);
  }
  out(ans)('\n');
  return 0;
}