Cod sursa(job #2070608)

Utilizator CobuzIonutCobuz Ionut-Alexandru CobuzIonut Data 19 noiembrie 2017 18:54:20
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>


using namespace std;

#define X first
#define Y second

vector <pair<int, int>> P;
int n;

long long calculDist(pair<int, int> a, pair<int, int> b)
{
    return (long long) ((a.X-b.X) * (a.X-b.X)+ (a.Y - b.Y) * (a.Y - b.Y));
}

bool cmp(pair<int,int> a, pair<int,int>b)
{
    return a.Y < b.Y;
}

long long DI(int st, int dr)
{
    if(dr - st == 1)
        return calculDist(P[st],P[dr]);
    else if(dr - st == 2)
    {
        long long d1 = calculDist(P[st],P[st+1]);
        long long minim = d1;
        long long d2 = calculDist(P[st],P[st+2]);
        if(d2 < minim )
            minim = d2;
        long long d3 = calculDist(P[st+1],P[st+2]);
        if(d3 < minim)
            minim = d3;
        return minim;
    }

    int m = (st + dr)/2,i,j;
    long long dist = min(DI(st,m),DI(m+1,dr));
    int delta = (int)(ceil(sqrt(dist)));

    vector<pair<int,int>> verif;
    for(i = st; i <= dr; i++)
        if(abs(P[i].X - P[m].X) <= delta)
            verif.push_back(P[i]);
    sort(verif.begin(),verif.end(),cmp);

    for(i = 0; i < verif.size(); i++)
        for(j = i+1; j<= i + 7 && j< verif.size(); j++)
            dist = min(dist, calculDist(verif[i],verif[j]));
    return dist;


}

int main()
{
    ifstream fin("cmap.in");
    ofstream fout("cmap.out");
    int x,y,i;
    fin>>n;

    for(i = 0; i < n; i++)
    {
        fin>>x>>y;
        P.push_back({x,y});
    }

    fout<<fixed<<setprecision(6)<<sqrt(DI(0,n-1));
    fin.close();
    fout.close();
    return 0;

}