Preparing for NOIP 1= ！！！#
Problem#
Solution#
$O(n^2)$ enumeration will definitely not work, consider optimizing with divide and conquer.
It's easy to calculate within each interval, the key is how to merge?
Let $h$ represent the minimum value returned by the two sub-intervals.
Look for points within distance $h$ near the $mid$ point, which may update the answer.
Just enumerate by the y-coordinate.
Discussion#
If TLE - Luogu | New Ecology of Computer Science Education (luogu.com.cn)
Code#
#include<bits/stdc++.h>
#define PII pair<long long, long long>
using namespace std;
#define x first
#define y second
const int N = 4e5 + 10;
PII p[N];
int n;
#define ll long long
long long merge(int l, int r)
{
// cout << l << " " << r << "----------\n";
if(l == r) return 0x3f3f3f3f3f3f3f3f;
int mid = (l + r) >> 1;
ll h1 = merge(l, mid);
ll h2 = merge(mid + 1, r);
ll h = min(h1, h2);
vector <PII> B;
for(int i = l;i <= r;i++)
{
if((p[i].x - p[mid].x) * (p[i].x - p[mid].x) < h) B.push_back({p[i].y, p[i].x});
}
sort(B.begin(), B.end());
// for(auto i : B)
// {
// cout << i.x << " " << i.y << endl;
// }
for(int i = 0;i < B.size();i++)
{
for(int q = i + 1;q < B.size();q++)
{
if((B[i].first - B[q].first) * (B[i].first - B[q].first) > h) break;
h = min(h, (B[i].first - B[q].first) * (B[i].first - B[q].first) + (B[i].second - B[q].second) * (B[i].second - B[q].second));
}
}
// cout << l << " " << r << " " << h << endl;
return h;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1;i <= n;i++)
cin >> p[i].x >> p[i].y;
sort(p + 1, p + 1 + n);
cout << merge(1, n) << endl;
return 0;
}