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
| #include <bits/stdc++.h>
#define int long long
#define double long double
#define pii pair<int, int>
#define N 200005
#define INF LONG_LONG_MAX
#define x first
#define y second
#define IOS ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
int n;
vector <pii> pt;
int dis(pii a,pii b){
int x = a.x - b.x,y = a.y - b.y;
return x * x + y * y;
}
bool cmp(pii a,pii b){
return a.y < b.y;
}
vector <pii> temp;
int solve(int l,int r){
if(l == r)return INF;
int mid = (l + r) / 2,mid_x = pt[mid].x;
int ans = min(solve(l,mid),solve(mid+1,r));
temp.assign(r - l + 1,{0 , 0});
merge(
pt.begin() + l,pt.begin() + mid + 1,
pt.begin() + mid + 1,pt.begin() + r + 1,
temp.begin(), cmp
);
for(int i=l;i<=r;i++)pt[i] = temp[i-l];
temp.clear();
for(int i=l;i<=r;i++){
if(abs(pt[i].x - mid_x)*abs(pt[i].x - mid_x) <= ans)temp.push_back(pt[i]);
}
int len = temp.size();
for(int i = 0;i < len;i++){
for(int j = i+1;j < len;j++){
ans = min(ans,dis(temp[i],temp[j]));
if(abs(temp[i].y - temp[j].y)*abs(temp[i].y - temp[j].y) > ans)break;
}
}
return ans;
}
signed main(){
IOS;
cin>>n;
pt.assign(n,{0,0});
for(int i=0;i<n;i++)cin>>pt[i].x>>pt[i].y;
sort(pt.begin(),pt.end());
cout<<solve(0,n-1)<<"\n";
}
|