Untitled

mail@pastecode.io avatar
unknown
plain_text
5 months ago
1.3 kB
5
Indexable
#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