Cod sursa(job #1022315)

Utilizator cdascaluDascalu Cristian cdascalu Data 5 noiembrie 2013 09:22:14
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#define Nmax 100001
#define INF 0x3f3f3f
using namespace std;

vector< pair<int,long long> > X,Y, vec,aux;
int N;
void read_data()
{
    FILE*f = fopen("cmap.in", "r");
    fscanf(f,"%d", &N);
    int x,y;
    for(int i=0;i<N;++i)
    {
        fscanf(f,"%d%d", &x,&y);
        X.push_back(make_pair(x,y));
    }
    fclose(f);
}
long long dist(pair<long long, long long> A, pair<long long, long long> B)
{
    return (A.first - B.first) * (A.first - B.first) + (A.second - B.second)*(A.second - B.second);
}
long long solve(int left, int right)
{
    long long ret;
    if(left >= right)
        return INF;
    if(right - left == 1)
    {
        if(Y[left] > Y[left + 1])
            swap(Y[left], Y[left+1]);
        return dist(X[left],X[right]);
    }
    int mid = (left + right)/2;
    ret = min(solve(left, mid), solve(mid, right));

    merge(Y.begin() + left, Y.begin() + mid+1, Y.begin() + mid+1, Y.begin() + right+1, vec.begin());
    copy(vec.begin(), vec.begin() + (right - left+1), Y.begin()+left);

    int size = 0;
    for(int i=left;i<=right;++i)
        if(abs(X[mid].first - Y[i].second) <= ret)
            vec[size++] = Y[i];

    for(int i=0;i<size;++i)
        for(int j=i+1;j<size && j-i < 8;++j)
            ret = min(ret, dist(Y[i], Y[j]));

    return ret;
}
int main()
{
    read_data();
    sort(X.begin(), X.end());
    vec.resize(N);
    aux.resize(N);
    for(int i=0;i<X.size();++i)
        Y.push_back(make_pair(X[i].second, X[i].first));

    FILE*g = fopen("cmap.out","w");
    fprintf(g, "%.6lf\n", sqrt(solve(0, N-1)));
    fclose(g);
    return 0;
}