Untitled
unknown
plain_text
18 days ago
1.3 kB
4
Indexable
Never
#include <bits/stdc++.h> using namespace std; long long calc(pair<long long, long long> point1, pair<long long, long long> point2) { return (point2.first - point1.first) * (point2.first - point1.first) + (point2.second - point1.second) * (point2.second - point1.second); } int main(){ long long n; long long minDis = LLONG_MAX; cin>>n; vector<pair<long long,long long>> points(n); for(long long i=0;i<n;i++){ cin>>points[i].first >> points[i].second; } sort(points.begin(),points.end()); set<pair<long long,long long>> apoints {{points[0].second,points[0].first}}; long long j=0; for(long long i=1;i<n;i++){ long long td = ceil(sqrt(minDis)); while(j<i && points[j].first < points[i].first -td){ apoints.erase({points[j].second,points[j].first}); j++; } auto lowerB = apoints.lower_bound({points[i].second-td,0}); auto upperB = apoints.upper_bound({points[i].second+td,0}); for(auto it=lowerB;it!=upperB;it++){ minDis = min(minDis,calc({it->second,it->first},points[i])); } apoints.insert({points[i].second,points[i].first}); } cout<< minDis <<endl; return 0; }
Leave a Comment