Cod sursa(job #3217841)

Utilizator Alex_Mihai10Mihai Alex-Ioan Alex_Mihai10 Data 24 martie 2024 20:49:03
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
#define MAX 100005
#define inf 2e9

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

struct point
{
    double x,y;
}pct[MAX],v[MAX];

bool crt1(point a,point b)
{
    return a.x<b.x;
}

bool crt2(point a,point b)
{
    return a.y<b.y;
}

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(dr-st<3)
    {
        double rez=inf;
        int i,j;
        for(i=st;i<dr;++i)
            for(j=i+1;j<=dr;++j)
                rez=min(rez,dist(pct[i],pct[j]));
        return rez;
    }
    else
    {
        int mij=(st+dr)/2;
        double rez1=divide(st,mij);
        double rez2=divide(mij+1,dr);
        double rez=min(rez1,rez2);
        int ind=0;
        int i;
        for(i=st;i<=dr;++i)
            if(fabs(pct[i].x-pct[mij].x)<=rez)
                v[++ind]=pct[i];
        sort(v+1,v+ind+1,crt2);
        int j;
        for(i=1;i<ind;++i)
            for(j=1;j<8;++j)
                rez=min(rez,dist(v[i],v[i+j]));
        return rez;
    }
}

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