Cod sursa(job #3292500)

Utilizator andrei1232008nicolae andrei andrei1232008 Data 8 aprilie 2025 13:33:35
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n,i;
double t;
struct punct
{
    double x,y;
}v[100100];
bool cmpx(punct a,punct b)
{
    return (a.x<b.x);
}
bool cmpy(punct a,punct b)
{
    return (a.y<b.y);
}
double dist(punct a,punct b)
{
    return abs(a.x-b.x)*abs(a.x-b.x)+abs(a.y-b.y)*abs(a.y-b.y);
}
void solve(int st,int dr)
{
    if(st==dr)return;
    int mid,i,j;
    vector <punct> a;
    mid=(st+dr)/2;
    solve(st,mid);
    solve(mid+1,dr);
    int midx=v[mid].x;
    for(i=st;i<=dr;i++)
    {
        if((v[i].x-midx)*(v[i].x-midx)<=t)
        a.push_back(v[i]);
    }
    sort(a.begin(),a.end(),cmpy);
    int s=a.size();
    for(i=0;i<s-1;i++)
        for(j=i+1;j<s;j++)
    {
        t=min(t,dist(v[i],v[j]));
    }
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,cmpx);
    t=1e18;
    solve(1,n);
    t=sqrt(t);
    fout<<fixed<<setprecision(6)<<t;
    return 0;
}