Cod sursa(job #3222193)

Utilizator MilitaruMihaiMihaiMIlitaru MilitaruMihai Data 9 aprilie 2024 11:43:34
Problema Cele mai apropiate puncte din plan Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n;
struct point
{
    int x,y;
} a[1000005];
point v[1000005];
int comp(point a,point b)
{
    return a.x<b.x || a.x==b.x && a.y<b.y;
}
int comp2(point a,point b)
{
    return a.y<b.y || a.y==b.y && a.x<b.x;
}
double dist(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double divide(int st,int dr)
{
    double mn=2e9;
    if (dr-st+1<=3)
    {
        for (int i=st; i<=dr; i++)
            for (int j=i+1; j<=dr; j++)
                mn=min(mn,dist(a[i],a[j]));
        return mn;
    }
    int mij=(st+dr)/2;
    double d1=divide(st,mij);
    double d2=divide(mij+1,dr);
    mn=min(d1,d2);
    int t=0;
    for (int i=st;i<=dr;i++)
    {
        if (abs(a[i].x-a[mij].x)<mn) v[++t]=a[i];
    }
    sort (v+1,v+t+1,comp2);
    for (int i=1;i<=t;i++)
       for (int j=i+1;j<=t;j++)
       {
           mn=min(mn,dist(v[i],v[j]));
       }
    return mn;
}
int main()
{
    fin>>n;
    for (int i=1; i<=n; i++)
        fin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,comp);
    fout<<fixed<<setprecision(6)<<divide(1,n);
    return 0;
}