Cod sursa(job #1419782)

Utilizator tudi98Cozma Tudor tudi98 Data 16 aprilie 2015 15:25:27
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>

using namespace std;

#define int64 long long
#define Pair pair<int64,int64>
#define x first
#define y second

const int Nmax = 100005;
const int inf = (1LL << 31) - 1;

Pair a[Nmax],b[Nmax],v[Nmax];
int N;

int64 dist(Pair A,Pair B) {
    return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}

int64 solve(int l,int r)
{
    if(l == r)
        return inf;

    if(r - l == 1)
        return dist(b[r],b[l]);

    int mid = (l + r) >> 1;
    int64 Ret = min(solve(l,mid),solve(mid+1,r));

    merge(b+l,b+mid+1,b+mid+1,b+r+1,v);
    copy(v,v+r-l+1,b+l);

    int Sz = 0;
    for(int i = l; i <= r; i++)
        if(abs(b[i].y - a[mid].x) <= Ret)
            v[++Sz] = b[i];

    for(int i = 1; i < Sz; i++)
        for(int j = i + 1; j <= Sz && j - i <= 7; j++)
            Ret = min(Ret,dist(v[i],v[j]));

    return Ret;
}

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

    fin >> N;
    for(int i = 0; i < N; i++) {
        int A,B;
        fin >> A >> B;
        a[i] = make_pair(A,B);
    }

    sort(a,a+N);
    
    for(int i = 0; i < N; i++)
        b[i] = make_pair(a[i].y,a[i].x);

    fout << fixed << setprecision(6) << sqrt((double)1LL*solve(0,N-1)) << "\n";

}