Cod sursa(job #3204269)

Utilizator alexdraguAlexandru Dragu alexdragu Data 16 februarie 2024 09:28:12
Problema Cele mai apropiate puncte din plan Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream cin("cmap.in");
ofstream cout("cmap.out");
long long n,i,ans=1e18;
struct elem
{
  int x,y;
}v[100005];
long long dist(elem a,elem b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int cmpx(elem a,elem b)
{
  return a.x<b.x;
}
int cmpy(elem a,elem b)
{
  return a.y<b.y;
}
void solve(long long st,long long dr)
{
  long long mij,x,i,j;
  if(st==dr) return;
  mij=(st+dr)/2;
  x=v[mij].x;
  solve(st,mij);
  solve(mij+1,dr);
  vector<elem> p;
  for(int i=st;i<=dr;i++)
        if((v[i].x-x)*(v[i].x-x)<=ans)
            p.push_back(v[i]);
  sort(p.begin(),p.end(),cmpy);
  for(int i=0;i<p.size();i++)
    {
        for(int j=i+1;j<p.size();j++)
        {
            if((p[j].y-p[i].y)*(p[j].y-p[i].y)>ans)
                break;
            ans=min(ans,dist(p[i],p[j]));
        }
    }
}
int main()
{
    cin>>n;
    for(i=1;i<=n;i++) cin>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmpx);
    solve(1,n);
    long double rez=sqrt((long double)ans);
    cout<<fixed<<setprecision(10)<<rez;
    return 0;
}