Cod sursa(job #2875182)

Utilizator alexmorosanuMorosanu Alexandru alexmorosanu Data 21 martie 2022 10:49:26
Problema Cele mai apropiate puncte din plan Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb

#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
long long dist(const pair <long long,long long> x,const pair <long long,long long> y)
{
    return (x.first-y.first)*(x.first-y.first)+(x.second-y.second)*(x.second-y.second);
}
long long INF=4e18;
vector <pair<long long,long long>> v(100011);
int vs;
long long divide(int st,int dr,vector <pair<long long,long long>> &a,vector <pair<long long,long long>> &b)
{
    if(st>=dr-1)
        return INF;
    if(dr-st==2)
    {
        if(b[st]>b[st+1])
            swap(b[st],b[st+1]);
        return dist(a[st],a[st+1]);
    }
    int mid=(st+dr)/2;
    long long sol=min(divide(st,mid,a,b),divide(mid,dr,a,b));
    sort(b.begin()+st,b.begin()+dr);
    int vs=0;
    for(int i=st;i<dr;i++)
        if(abs(b[i].second-a[mid].first)<=sol)
        {
            v[vs]=b[i];
            vs++;
        }
    for(int i=0;i<vs-1;i++)
        for(int j=i+1;j<vs && j-i<8;j++)
            sol=min(sol,dist(v[i],v[j]));
    return sol;
}
vector <pair<long long,long long>> a,b;
long long x,y;
int n,i;
int main()
{
    f>>n;
    a.resize(n);
    b.resize(n);
    for(i=1;i<=n;i++)
        f>>a[i].first>>a[i].second;
    sort(a.begin(),a.end());
    for(i=0;i<a.size();i++)
        b[i]=make_pair(a[i].second,a[i].first);
    g<<fixed<<setprecision(6)<<sqrt(divide(0,n,a,b));
    return 0;
}