Cod sursa(job #3222195)

Utilizator MilitaruMihaiMihaiMIlitaru MilitaruMihai Data 9 aprilie 2024 11:49:44
Problema Cele mai apropiate puncte din plan Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 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
{
    double 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)
{
    if (st==dr) return 2e9;
    int mij=(st+dr)/2;
    double d1=divide(st,mij);
    double d2=divide(mij+1,dr);
    double 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 && dist(a[i],a[j])<=mn;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;
}