Cod sursa(job #2067608)

Utilizator andronierRobu Stefan andronier Data 16 noiembrie 2017 17:29:47
Problema Cele mai apropiate puncte din plan Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<algorithm>
#include<iomanip>

using namespace std;

ifstream f("cmap.in");
ofstream g("cmap.out");

long long const oo = 1LL*1<<60;

struct point
{
    int x,y;
};

point P[100005], Aux[10005];
int n;

bool operator <(point A, point B)
{
    if(A.x != B.x)
        return A.x < B.x;
    else
        return A.y < B.y;
}
void Read()     // citeste n puncte
{
    int i, x, y;

    f >> n;

    point a;                //citim cele n puncte

    for(i = 0 ; i < n ; i++)
    {
        f >> x >> y;
        a.x = x;
        a.y = y;
        P[i] = a;
    }
    sort(P , P + n);         // sortam crescator cele n puncte dupa x, iar daca x-urile sunt egale,sortam crescator dupa y
}

long long dist(point A, point B)          // distanta euclidiana calculata ca longlong,dar fara radical
{
    return 1LL * (B.x - A.x) * (B.x - A.x) + 1LL * (B.y - A.y) * (B.y - A.y);
}

long long divide(int st,int dr)
{
    if( st >= dr)
        return oo;
    if( dr - st <= 2)
       {
           long long mini = oo;
           for(int i = st; i <= dr; ++i)
                for(int j = i + 1; j <= dr; ++j)
                    mini = min(mini, dist(P[i], P[j]));
           return mini;
       }

    int m = (st + dr) / 2,k=0;
    long long a,b,c;
    a = oo;

    b = divide(st, m);
    c = divide(m, dr);
    a = min(b, c);

    for(int i = m; i >= st && P[m].x - P[i].x <= a; i--)
        Aux[k++] = P[i];

    for(int i = m + 1; i <= dr && P[i].x - P[m].x <= a; i++)
        Aux[k++] = P[i];

    sort(Aux+1 , Aux + k);
    for(int i = 0; i < k; ++i)
        for(int j = i + 1; j < i + 8 && j < k; ++j)
            a = min(a, dist(P[i], P[j]));

    return a;
}


int main()
{
    Read();
    g<<fixed<<setprecision(6)<<sqrt(divide(0,n-1));

    return 0;
}