Cod sursa(job #3345910)

Utilizator Gabriel_DaescuDaescu Gabriel Florin Gabriel_Daescu Data 11 martie 2026 19:09:22
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.25 kb
#include <bits/stdc++.h>
#define NMAX 100006
using namespace std;
ifstream  fin("cmap.in");
ofstream fout("cmap.out");
int n;

struct punct
{
    double x,y;
} v[NMAX];

bool cmp1(punct a, punct b)
{
    if(a.x!=b.x)
    {
        return a.x<b.x;
    }
    else
    {
        return a.y<b.y;
    }
}

bool cmp2(punct a, punct b)
{
    return a.y<b.y;
}

void citire()
{
    fin>>n;

    for(int i=1; i<=n; i++)
    {
        fin>>v[i].x>>v[i].y;
    }
}

double dist(punct a, punct b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void interclasare(int st, int pmijl, int dr)
{
    vector<punct> aux(dr-st+1);

    int i,j,k;
    i=st;
    j=pmijl+1;
    k=0;

    while(i<=pmijl && j<=dr)
    {
        if(v[i].y<v[j].y)
        {
            aux[k++]=v[i++];
        }
        else
        {
            aux[k++]=v[j++];
        }
    }

    while(i<=pmijl)
    {
        aux[k++]=v[i++];
    }

    while(j<=dr)
    {
        aux[k++]=v[j++];
    }

    for(int t=0; t<k; t++)
    {
        v[st+t]=aux[t];
    }
}

double divide_et_impera(int st, int dr)
{
    if(dr-st<=3)
    {
        double d=100000000;
        d=d*10000000;

        for(int i=st; i<dr; i++)
        {
            for(int j=i+1; j<=dr; j++)
            {
                d=min(d,dist(v[i],v[j]));
            }
        }

        sort(v+st,v+dr+1,cmp2);
        return d;
    }
    else
    {
        int pmijl=(st+dr)/2;
        double mid=v[pmijl].x;

        double d=min(divide_et_impera(st,pmijl),divide_et_impera(pmijl+1,dr));

        interclasare(st,pmijl,dr);

        vector<punct> banda;

        for(int i=st; i<=dr; i++)
        {
            if(abs(v[i].x-mid)<d)
            {
                banda.push_back(v[i]);
            }
        }

        for(int i=0; i<banda.size(); i++)
        {
            for(int j=i+1; j<banda.size() && banda[j].y-banda[i].y<d; j++)
            {
                d=min(d,dist(banda[i],banda[j]));
            }
        }

        return d;
    }
}

int main()
{
    citire();

    sort(v+1,v+1+n,cmp1);

    double dmin=divide_et_impera(1,n);

    fout<< fixed << setprecision(6) << dmin << "\n";

    return 0;
}