Nt_Tsumiki @ 2024-02-21 14:51:18
写的 KDT，被卡了
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define int long long
namespace Octane {
//non terrae plus ultra dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#define OCTANE // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#define BUFFER_SIZE 100000 // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#define ll long long // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#define db double // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#define ldb long double // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
char ibuf[100000], obuf[100000], *p1=ibuf,*p2=ibuf,*p3=obuf;
#ifdef ONLINE_JUDGE//dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#define getchar() ((p1==p2) and (p2=(p1=ibuf)+fread(ibuf,1,\
BUFFER_SIZE,stdin),p1==p2)?(EOF):(*p1++)) // dqrdqrdqrdqrdqr
#define putchar(x) ((p3==obuf+BUFFER_SIZE) && (fwrite(obuf,\
p3-obuf,1,stdout),p3=obuf),*p3++=x) // dqrdqrdqrdqrdqrdqrdqr
#endif// fread in OJ, getchar in local dqrdqrdqrdqrdqrdqrdqr
#define isdigit(ch) (ch>47&&ch<58)//dqrdqrdqrdqrdqrdqrdqrdqr
#define isspace(ch) (ch<=32&&ch!=EOF)//dqrdqrdqrdqrdqrdqrdqr
#define isseen(ch) (ch>32) // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
struct Octane_t{~Octane_t(){fwrite(obuf,p3-obuf, 1, stdout);
}bool flag=false;operator bool(){return flag;} }io; template
<typename T>inline T read(){T s=0; int w = 1; char ch; while
(ch=getchar(), !isdigit(ch)&&(ch!=EOF))if(ch == '-') w = -1;
if(ch == EOF) return 0; while(isdigit(ch)) s = s*10+ch-48,ch
=getchar(); return s *= w; } template<typename T>inline bool
read(T &s) { s = 0; int w = 1; char ch; while(ch = getchar()
,!isdigit(ch)&&(ch!=EOF))if(ch == '-') w = -1; if(ch == EOF)
return false;while(isdigit(ch))s = s*10+ch-48, ch=getchar();
return s*=w,true;}inline bool read(char &s){while(s= getchar
(), isspace(s)); return s != EOF; } inline bool read(char *s
){char ch=getchar();while(isspace(ch))ch= getchar();if(ch ==
EOF)return false;while(isseen(ch)) *s++ = ch, ch= getchar();
*s='\000';return true;}template<typename T> void printv(T a)
{if(a== 0){ putchar('0'); return void(); }static char st[65]
; int top = 0; if (a < 0) putchar ('-'), a = - a; while(a)st
[++top]='0'+a%10,a/=10;while(top)putchar(st[top--]);} inline
void printv(char c){putchar(c);}inline void printv(char *s){
for(int i=0;s[i];i++)putchar(s[i]);}inline void printv(const
char *s){ for(int i=0;s[i];i++) putchar(s[i]); } inline void
printv(bool a){ if(a != 0)putchar('1'); else putchar('0'); }
#ifdef _GLIBCXX_STRING // support for string dqrdqrdqrdqrdqr
inline bool read(std::string& s) { s = ""; char ch; while(ch
=getchar(), isspace(ch)); if(ch == EOF) return false; while(
!isspace(ch)) s+=ch,ch=getchar(); return true; } inline bool
getline(Octane_t &io,std::string s){s="";char ch= getchar();
if(ch==EOF)return false;while(ch!='\n' and ch !=EOF)s+=ch,ch
=getchar();return true;}inline void printv(const std::string
&a){for(auto i = a.begin(); i != a.end(); ++i) putchar(*i);}
#endif// dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
template<typename T>inline void print(const char *p,T first)
{ int n = strlen(p) - 1; for(int i = 0; i <= n; i++) { if(p[
i] == '`') { putchar(p[++ i]); continue; } else if ( p[i] ==
'{'){printv(first); i++; continue; } else putchar(p[i]); } }
#if __cplusplus >= 201103L // support for many values dqrdqr
template<typename T,typename... T1>inline int read(T& a, T1&
...other){return read(a)+read(other...); } inline void print
(const char *p) { printv(p); }template<typename T1, typename
... T2>void print(const char*p, T1 first, T2 ...other) { int
n=strlen(p)-1; for(int i = 0; i <= n; i++) { if(p[i] == '`')
{putchar(p[++i]);continue;}else if(p[i]=='{'){printv(first);
print(p+i+2,other...);return void();}else putchar(p[i]); } }
#endif // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdq
template <typename T> Octane_t& operator >> (Octane_t &io, T
&b){return io.flag=read(b),io;}Octane_t& operator>>(Octane_t
&io, char *b){return io.flag=read(b), io;} template<typename
T>Octane_t&operator<<(Octane_t&io,T b){return printv(b),io;}
#define cout io// dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#define cin io // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#define endl '\n' // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#undef ll// dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#undef db// dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#undef ldb//dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
} using namespace Octane;
using namespace std;
int n,x[400001],y[400001];
struct KD_tree {
#define N 400001
#define INF 1e18
struct Point;
struct Tree;
int tcnt,rubcnt,flatcnt,rt,rub[N];
bool flag;
struct Point {
int c[2];
int operator[](int x) { return c[x]; }
void operator=(Tree tr) { c[0]=tr[0],c[1]=tr[1]; }
}flat_p[N];
struct Tree {
int ls,rs,c[2],maxn[2],minn[2];
int operator[](int x) { return c[x]; }
void operator=(Point poi) { c[0]=poi[0],c[1]=poi[1],ls=rs=maxn[0]=maxn[1]=minn[0]=minn[1]=0; }
}t[N];
void upd(int x) {
t[x].maxn[0]=t[x].minn[0]=t[x][0],t[x].maxn[1]=t[x].minn[1]=t[x][1];
for (int i:{0,1}) {
if (t[x].ls)
t[x].maxn[i]=max(t[x].maxn[i],t[t[x].ls].maxn[i]),
t[x].minn[i]=min(t[x].minn[i],t[t[x].ls].minn[i]);
if (t[x].rs)
t[x].maxn[i]=max(t[x].maxn[i],t[t[x].rs].maxn[i]),
t[x].minn[i]=min(t[x].minn[i],t[t[x].rs].minn[i]);
}
}
void build(int &x,int l,int r,int d) {
x=rub[rubcnt--]; int mid=(l+r)>>1;
nth_element(flat_p+l,flat_p+mid,flat_p+r+1,[d](Point p1,Point p2){ return p1[d]<p2[d]; });
t[x]=flat_p[mid];
if (l<mid) build(t[x].ls,l,mid-1,d^1);
if (r>mid) build(t[x].rs,mid+1,r,d^1);
upd(x);
}
int ndis;
int dis(Tree tr,Point poi) { return (tr[0]-poi[0])*(tr[0]-poi[0])+(tr[1]-poi[1])*(tr[1]-poi[1]); }
int __ndis(Tree tr,Point poi) {
int res=0;
if (tr.minn[0]<=poi[0] and poi[0]<=tr.maxn[0]) res+=0;
else res+=min((tr.maxn[0]-poi[0])*(tr.maxn[0]-poi[0]),(tr.minn[0]-poi[0])*(tr.minn[0]-poi[0]));
if (tr.minn[1]<=poi[1] and poi[1]<=tr.maxn[1]) res+=0;
else res+=min((tr.maxn[1]-poi[1])*(tr.maxn[1]-poi[1]),(tr.minn[1]-poi[1])*(tr.minn[1]-poi[1]));
return res;
}
void askn(int x,Point poi) {
if (!x) return;
if ((t[x][0]!=poi[0] or t[x][1]!=poi[1]) or flag) ndis=min(ndis,dis(t[x],poi));
else flag=1;
int disls=__ndis(t[t[x].ls],poi),disrs=__ndis(t[t[x].rs],poi);
if (disls<disrs and disls<ndis) {
askn(t[x].ls,poi);
if (disrs<ndis) askn(t[x].rs,poi);
} else if (disrs<=disls and disrs<ndis) {
askn(t[x].rs,poi);
if (disls<ndis) askn(t[x].ls,poi);
}
}
void init() { for (int i=1;i<N;i++) rub[++rubcnt]=i; }
void ins(int x,int y) { flat_p[++flatcnt]=Point{x,y}; }
void build() { build(rt,1,flatcnt,0); }
int askn(int x,int y) { ndis=INF,flag=0; askn(rt,Point{x,y}); return ndis; }
#undef INF
#undef N
}t;
signed main() {
cin>>n; t.init();
for (int i=1;i<=n;i++) {
cin>>x[i]>>y[i];
t.ins(x[i],y[i]);
}
t.build();
int ans=1e18;
for (int i=1;i<=n;i++) ans=min(ans,t.askn(x[i],y[i]));
cout<<ans<<'\n';
return 0;
}by int_R @ 2024-02-21 15:29:23
本来就卡的很难过了吧，这个不是让你写分治的吗
by Nt_Tsumiki @ 2024-02-21 15:56:27
@int_R 主要是有人用 kdt 过去了（
by Nt_Tsumiki @ 2024-02-21 15:56:53
而且我跟他写的还差不多（
by Estelle_N @ 2024-02-21 16:01:48
@Nt_Tsumiki 你别 #define int long long 啊
by Nt_Tsumiki @ 2024-02-21 16:03:13
@Estelle_N 彳亍
by Estelle_N @ 2024-02-21 16:14:47
@Nt_Tsumiki 145pts了
by Nt_Tsumiki @ 2024-02-21 16:15:58
@Estelle_N
卡到极限了（
142pts（
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
namespace Octane {
//non terrae plus ultra dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#define OCTANE // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#define BUFFER_SIZE 100000 // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#define ll long long // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#define db double // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#define ldb long double // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
char ibuf[100000], obuf[100000], *p1=ibuf,*p2=ibuf,*p3=obuf;
#ifdef ONLINE_JUDGE//dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#define getchar() ((p1==p2) and (p2=(p1=ibuf)+fread(ibuf,1,\
BUFFER_SIZE,stdin),p1==p2)?(EOF):(*p1++)) // dqrdqrdqrdqrdqr
#define putchar(x) ((p3==obuf+BUFFER_SIZE) && (fwrite(obuf,\
p3-obuf,1,stdout),p3=obuf),*p3++=x) // dqrdqrdqrdqrdqrdqrdqr
#endif// fread in OJ, getchar in local dqrdqrdqrdqrdqrdqrdqr
#define isdigit(ch) (ch>47&&ch<58)//dqrdqrdqrdqrdqrdqrdqrdqr
#define isspace(ch) (ch<=32&&ch!=EOF)//dqrdqrdqrdqrdqrdqrdqr
#define isseen(ch) (ch>32) // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
struct Octane_t{~Octane_t(){fwrite(obuf,p3-obuf, 1, stdout);
}bool flag=false;operator bool(){return flag;} }io; template
<typename T>inline T read(){T s=0; int w = 1; char ch; while
(ch=getchar(), !isdigit(ch)&&(ch!=EOF))if(ch == '-') w = -1;
if(ch == EOF) return 0; while(isdigit(ch)) s = s*10+ch-48,ch
=getchar(); return s *= w; } template<typename T>inline bool
read(T &s) { s = 0; int w = 1; char ch; while(ch = getchar()
,!isdigit(ch)&&(ch!=EOF))if(ch == '-') w = -1; if(ch == EOF)
return false;while(isdigit(ch))s = s*10+ch-48, ch=getchar();
return s*=w,true;}inline bool read(char &s){while(s= getchar
(), isspace(s)); return s != EOF; } inline bool read(char *s
){char ch=getchar();while(isspace(ch))ch= getchar();if(ch ==
EOF)return false;while(isseen(ch)) *s++ = ch, ch= getchar();
*s='\000';return true;}template<typename T> void printv(T a)
{if(a== 0){ putchar('0'); return void(); }static char st[65]
; int top = 0; if (a < 0) putchar ('-'), a = - a; while(a)st
[++top]='0'+a%10,a/=10;while(top)putchar(st[top--]);} inline
void printv(char c){putchar(c);}inline void printv(char *s){
for(int i=0;s[i];i++)putchar(s[i]);}inline void printv(const
char *s){ for(int i=0;s[i];i++) putchar(s[i]); } inline void
printv(bool a){ if(a != 0)putchar('1'); else putchar('0'); }
#ifdef _GLIBCXX_STRING // support for string dqrdqrdqrdqrdqr
inline bool read(std::string& s) { s = ""; char ch; while(ch
=getchar(), isspace(ch)); if(ch == EOF) return false; while(
!isspace(ch)) s+=ch,ch=getchar(); return true; } inline bool
getline(Octane_t &io,std::string s){s="";char ch= getchar();
if(ch==EOF)return false;while(ch!='\n' and ch !=EOF)s+=ch,ch
=getchar();return true;}inline void printv(const std::string
&a){for(auto i = a.begin(); i != a.end(); ++i) putchar(*i);}
#endif// dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
template<typename T>inline void print(const char *p,T first)
{ int n = strlen(p) - 1; for(int i = 0; i <= n; i++) { if(p[
i] == '`') { putchar(p[++ i]); continue; } else if ( p[i] ==
'{'){printv(first); i++; continue; } else putchar(p[i]); } }
#if __cplusplus >= 201103L // support for many values dqrdqr
template<typename T,typename... T1>inline int read(T& a, T1&
...other){return read(a)+read(other...); } inline void print
(const char *p) { printv(p); }template<typename T1, typename
... T2>void print(const char*p, T1 first, T2 ...other) { int
n=strlen(p)-1; for(int i = 0; i <= n; i++) { if(p[i] == '`')
{putchar(p[++i]);continue;}else if(p[i]=='{'){printv(first);
print(p+i+2,other...);return void();}else putchar(p[i]); } }
#endif // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdq
template <typename T> Octane_t& operator >> (Octane_t &io, T
&b){return io.flag=read(b),io;}Octane_t& operator>>(Octane_t
&io, char *b){return io.flag=read(b), io;} template<typename
T>Octane_t&operator<<(Octane_t&io,T b){return printv(b),io;}
#define cout io// dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#define cin io // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#define endl '\n' // dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#undef ll// dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#undef db// dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
#undef ldb//dqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqrdqr
} using namespace Octane;
using namespace std;
int n,x[400001],y[400001];
struct KD_tree {
#define N 400001
#define INF 1e18
struct Point;
struct Tree;
int tcnt,flatcnt,rt;
struct Point {
long long c[2];
long long operator[](int x) { return c[x]; }
void operator=(Tree tr) { c[0]=tr[0],c[1]=tr[1]; }
}flat_p[N];
struct Tree {
int ls,rs;
int c[2],maxn[2],minn[2];
int operator[](int x) { return c[x]; }
void operator=(Point poi) { c[0]=poi[0],c[1]=poi[1]; }
}t[N];
void upd(int x) {
t[x].maxn[0]=t[x].minn[0]=t[x][0],t[x].maxn[1]=t[x].minn[1]=t[x][1];
if (t[x].ls)
t[x].maxn[0]=max(t[x].maxn[0],t[t[x].ls].maxn[0]),
t[x].minn[0]=min(t[x].minn[0],t[t[x].ls].minn[0]),
t[x].maxn[1]=max(t[x].maxn[1],t[t[x].ls].maxn[1]),
t[x].minn[1]=min(t[x].minn[1],t[t[x].ls].minn[1]);
if (t[x].rs)
t[x].maxn[0]=max(t[x].maxn[0],t[t[x].rs].maxn[0]),
t[x].minn[0]=min(t[x].minn[0],t[t[x].rs].minn[0]),
t[x].maxn[1]=max(t[x].maxn[1],t[t[x].rs].maxn[1]),
t[x].minn[1]=min(t[x].minn[1],t[t[x].rs].minn[1]);
}
void build(int &x,int l,int r,int d) {
x=++tcnt; int mid=(l+r)>>1;
nth_element(flat_p+l,flat_p+mid,flat_p+r+1,[d](Point p1,Point p2){ return p1[d]<p2[d]; });
t[x]=flat_p[mid];
if (l<mid) build(t[x].ls,l,mid-1,d^1);
if (r>mid) build(t[x].rs,mid+1,r,d^1);
upd(x);
}
long long ndis;
inline long long min(long long x,long long y) { return x<y?x:y; }
inline long long max(long long x,long long y) { return x>y?x:y; }
inline long long dis(Tree tr,Point poi) { return (tr[0]-poi[0])*(tr[0]-poi[0])+(tr[1]-poi[1])*(tr[1]-poi[1]); }
inline long long __ndis(Tree tr,Point poi) {
return (tr.minn[0]<=poi[0] and poi[0]<=tr.maxn[0]?0:min((tr.maxn[0]-poi[0])*(tr.maxn[0]-poi[0]),(tr.minn[0]-poi[0])*(tr.minn[0]-poi[0])))
+(tr.minn[1]<=poi[1] and poi[1]<=tr.maxn[1]?0:min((tr.maxn[1]-poi[1])*(tr.maxn[1]-poi[1]),(tr.minn[1]-poi[1])*(tr.minn[1]-poi[1])));
}
void askn(int x,Point poi) {
if (!x) return;
if (t[x][0]!=poi[0] or t[x][1]!=poi[1]) ndis=min(ndis,dis(t[x],poi));
long long disls=t[x].ls?__ndis(t[t[x].ls],poi):INF,disrs=t[x].rs?__ndis(t[t[x].rs],poi):INF;
if (disls<disrs and disls<ndis) {
askn(t[x].ls,poi);
if (disrs<ndis) askn(t[x].rs,poi);
} else if (disrs<=disls and disrs<ndis) {
askn(t[x].rs,poi);
if (disls<ndis) askn(t[x].ls,poi);
}
}
void ins(int x,int y) { flat_p[++flatcnt]=Point{x,y}; }
void build() { build(rt,1,flatcnt,0); }
long long askn(int x,int y) { ndis=INF; askn(rt,Point{x,y}); return ndis; }
#undef INF
#undef N
}t;
signed main() {
cin>>n;
for (int i=1;i<=n;++i) {
cin>>x[i]>>y[i];
t.ins(x[i],y[i]);
}
t.build();
long long ans=1e18;
for (int i=1;i<=n;++i) ans=min(ans,t.askn(x[i],y[i]));
cout<<ans<<'\n';
return 0;
}by Nt_Tsumiki @ 2024-02-21 16:23:20
@Estelle_N 论
if (clock() * 1.0 / CLOCKS_PER_SEC >= 0.34) break; 为什么是神
by Estelle_N @ 2024-02-21 16:25:51
@Nt_Tsumiki 啥呀 我代码也没有这句话吧
by Nt_Tsumiki @ 2024-02-21 16:26:37
@Estelle_N 不是我是指加上它就过了（