Cod sursa(job #3204279)

Utilizator bagae123Burlacu Andrei bagae123 Data 16 februarie 2024 09:45:24
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct point
{
    int x,y;

} v[100001],pts[100001];
long long ans=1e18;
int comparx(point a,point b)
{
    return (a.x<b.x)||(a.x==b.x&&a.y<b.y);
}
int compary(point a,point b)
{
    return (a.y<b.y)||(a.y==b.y&&a.x<b.x);
}
long long dist(point a,point b)
{return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);

}
void solve(int st,int dr)
{
    int mij,i;
    mij=(st+dr)/2;if(st==dr)return;
int x=v[mij].x;
    solve(mij+1,dr);
    solve(st,mij);
    int    nr=0;
    for(i=st; i<=dr; i++)
    {
        if((v[i].x-x)*(v[i].x-x)<=ans)
    {
        nr++;
        pts[nr].x=v[i].x;
            pts[nr].y=v[i].y;
        }

    }sort(pts+1,pts+nr+1,compary);
    for(i=1;i<=nr;i++)
    {
        for(int j=i+1;j<=nr;j++)
        {
            if((pts[j].y-pts[i].y)*(pts[j].y-pts[i].y)>ans)break;
            ans=min(ans,dist(pts[i],pts[j]));
        }
    }



}
int main()
{
int n,i;
fin>>n;
for(i=1;i<=n;i++)
{
    fin>>v[i].x>>v[i].y;
}sort(v+1,v+n+1,comparx);
solve(1,n);

fout<<fixed<<setprecision(6)<<sqrt(ans);
    return 0;
}