Cod sursa(job #2911007)

Utilizator mihneazzzMacovei Daniel mihneazzz Data 26 iunie 2022 13:03:41
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include<bits/stdc++.h>
#define N 100005
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");

struct punct
{
    int x,y;
}a[N],b[N];
bool comp_x(punct x,punct y)
{
    return x.x<y.x;
}
bool comp_y(punct x,punct y)
{
    return x.y<y.y;
}
double dist(punct x,punct y)
{
   return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double combine(int st, int dr, double lungime)
{
    double m=lungime;
    int ct=0,mij = (st+dr)/2;
    for(int i=st; i<=dr; i++)
        if(abs(a[i].x - a[mij].x) < lungime)
            b[++ct]=a[i];
    sort(b+1,b+ct+1,comp_y);
    for(int i=1; i<ct; i++)
        for(int j=i+1; j<=ct && j<=i+7; j++)
            m= min(m,dist(b[i],b[j]));
    return m;
}
double divide_et_impera(int st, int dr)
{
    double m;
    if(dr-st <= 2)
    {
        m = dist(a[st],a[st+1]);
        if(dr-st == 2)
        {
            m= min(m, dist(a[st],a[st+2]));
            m= min(m, dist(a[st+1],a[st+2]));
        }
        return m;
    }
    int mij = (st+dr)/2;
    m = min(divide_et_impera(st, mij), divide_et_impera(mij+1, dr));
    m = min(m, combine(st, dr, m));
    return m;
}

int main()
{
    int n,i;
    fin>>n;
    for(i=1; i<=n; i++)
        fin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,comp_x);
    fout<<setprecision(6)<<fixed<<divide_et_impera(1, n);
    return 0;

}