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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
ll (ll x,ll y) {return x<y?x:y;}
ll mymax(ll x,ll y) {return x>y?x:y;}
ll myabs(ll x) {return x>0?x:-x;}
ll mysqr(ll x) {return x*x;}
const int MAXN=51000;
const int INF=0x3f3f3f3f;
struct nod
{
ll d[2];
ll mi[2],mx[2];
int son[2];
nod()
{
son[0]=son[1]=0;
}
}p[MAXN];
int D;
bool cmp(nod a,nod b)
{
return (a.d[D]<b.d[D]) or (a.d[D]==b.d[D] and a.d[1-D]<b.d[1-D]);
}
void update(int f,int x)
{
p[f].mi[0]=mymin(p[f].mi[0],p[x].mi[0]);p[f].mx[0]=mymax(p[f].mx[0],p[x].mx[0]);
p[f].mi[1]=mymin(p[f].mi[1],p[x].mi[1]);p[f].mx[1]=mymax(p[f].mx[1],p[x].mx[1]);
}
ll getdis(int t,ll x,ll y)
{
ll xx=mymax(0,p[t].mi[0]-x)+mymax(0,x-p[t].mx[0]);
ll yy=mymax(0,y-p[t].mx[1])+mymax(0,p[t].mi[1]-y);
return xx*xx+yy*yy;
}
int root;
int build(int l,int r,int d)
{
if(l>r) return 0;
int mid=(l+r)/2;
D=d;nth_element(p+l,p+mid,p+r+1,cmp);
p[mid].mi[0]=p[mid].mx[0]=p[mid].d[0];
p[mid].mi[1]=p[mid].mx[1]=p[mid].d[1];
if(l<=mid-1) p[mid].son[0]=build(l,mid-1,1-d),update(mid,p[mid].son[0]);
if(mid+1<=r) p[mid].son[1]=build(mid+1,r,1-d),update(mid,p[mid].son[1]);
return mid;
}
int cnt;
void insert(ll x,ll y)
{
int t=++cnt;
p[t].d[0]=p[t].mi[0]=p[t].mx[0]=x;
p[t].d[1]=p[t].mi[1]=p[t].mx[1]=y;
if(root==0) root=t;
else
{
int f=root;
for(D=0;1;D=1-D)
{
update(f,t);
int tmp=cmp(p[f],p[t]);
if(p[f].son[tmp]==0)
{
p[f].son[tmp]=t;
break;
}
f=p[f].son[tmp];
}
}
}
ll ans;
void ask(int t,ll x,ll y)
{
ll dis=mysqr(p[t].d[0]-x)+mysqr(p[t].d[1]-y);
if(dis!=0) ans=mymin(ans,dis);
int lc=p[t].son[0],rc=p[t].son[1];
ll f[2];
f[0]=(lc>0)?getdis(lc,x,y):INF;
f[1]=(rc>0)?getdis(rc,x,y):INF;
bool tmp=(f[1]<=f[0]);
if(f[tmp]<ans) ask(p[t].son[tmp],x,y);
if(f[1-tmp]<ans) ask(p[t].son[1-tmp],x,y);
}
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i].d[0],&p[i].d[1]);
root=build(1,n,0);
ans=INF;
for(int i=1;i<=n;i++) ask(root,p[i].d[0],p[i].d[1]);
printf("%.4lf",sqrt(double(ans)));
}
|
近期评论