Cod sursa(job #3230141)

Utilizator Cezar2009Cezar Mihai Titihazan Cezar2009 Data 19 mai 2024 13:35:44
Problema Cele mai apropiate puncte din plan Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
//https://infoarena.ro/problema/cmap
#include <bits/stdc++.h>
using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

vector <pair<int64_t,int64_t>> v;
int64_t dis=1000000000000;
bool compararex(pair<int64_t,int64_t> a,pair<int64_t,int64_t> b)
{
    if(a.first<b.first)
        return 1;
    else
        return 0;
}
bool compararey(pair<int64_t,int64_t> a,pair<int64_t,int64_t> b)
{
    if(a.second<b.second)
        return 1;
    else
        return 0;
}
int64_t distanta(pair<int64_t,int64_t> a,pair<int64_t,int64_t> b)
{
    return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
void recursivitate(int64_t st,int64_t dr)
{
    if(st==dr)
        return;
    int64_t mij,i,j;
    mij=(st+dr)/2;
    recursivitate(st,mij);
    recursivitate(mij+1,dr);
    vector <pair<int64_t,int64_t>> c;
    for(i=st;i<=dr;++i)
    {
        if((v[i].first-v[mij].first)*(v[i].first-v[mij].first)<=dis)
        {
            c.push_back(v[i]);
        }
    }
    sort(c.begin(),c.end(),compararey);
    for(i=0;i<c.size();++i)
    {
        for(j=i+1;((j<c.size())&&(c[j].second-c[i].second)*(c[j].second-c[i].second)<=dis);++j)
        {
            if(dis>distanta(c[i],c[j]))
            {
                dis=distanta(c[i],c[j]);
            }
        }
    }
}
int main()
{
    int64_t i,n,x,y;
    fin>>n;
    for(i=0;i<n;i++)
    {
        fin>>x>>y;
        v.emplace_back(x,y);
    }
    sort(v.begin(),v.end(),compararex);
    recursivitate(0,n-1);
    fout<<fixed<<setprecision(6)<<sqrt(dis);
//    for(i=0;i<n;i++)
//    {
//        cout<<v[i].first<<" "<<v[i].second<<"\n";
//    }
    return 0;
}