Cod sursa(job #1042051)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 26 noiembrie 2013 15:38:42
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.94 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#define NMax 100010
#define INF 8000000000000000000LL
#define limit 1000000
#define Next ++position == limit?f.read(buffer, limit), position = 0:0

using namespace std;

ifstream f ("cmap.in");
int n;
int position;
char buffer[limit];
pair<int, int> X[NMax], Y[NMax], aux[NMax];

inline void Read(int &x)
{
    for (; buffer[position] < '0' || buffer[position] > '9'; Next);
    for (x = 0; '0' <= buffer[position] && buffer[position] <= '9'; x = x*10 + buffer[position] - '0', Next);
}

void Read()
{
    Read(n);
    for (int i = 0; i<n; ++i)
        Read(X[i].first), Read(X[i].second);
    sort(X, X+n);
    for (int i = 0; i<n; ++i)
        Y[i] = make_pair(X[i].second, X[i].first);
}

inline long long sqr(const int x)
{
    return 1LL*x*x;
}

inline long long Dist(const pair<int, int> A, const pair<int, int> B)
{
    return sqr(A.first - B.first) + sqr(A.second - B.second);
}

inline long long cmap(const int st, const int dr)
{
    /// returneaza distanta celor mai apropiate 2 puncte din multimea [st, dr) din vectorul X sortat dupa x

    /*if (dr - st <= 1) <=> (dr <= st + 1) <=> (st >= dr - 1)*/
    /// daca am doar un punct in setul meu sau daca st a depasit dr atunci returnez infinit
    if (st >= dr - 1)
        return INF;

    /// daca am doua puncte atunci le sortez dupa y in vectorul Y si returnez distanta dintre ele
    if (dr - st == 2)
    {
        sort (Y+st, Y+dr);
        return Dist(X[st], X[st+1]);
    }

    int i, j, mij;
    long long distance;
    mij = (st+dr)>>1;
    distance = min (cmap(st, mij), cmap(mij, dr));

    ///interclasam in vectorul aux vectorii Ys si Yd corespunzatori celor 2 impartiri ale planului efectuate
    merge(Y+st, Y+mij, Y+mij, Y+dr, aux);
    /// copiem la pozitia st in vectorul Y pe aux care reprezinta interclasarea lui Ys si Yd
    copy(aux, aux+dr-st, Y+st);

    /// selectam fasia de latime 2*distance in jurul dreptei alese
    int len = 0;
    for (i=st; i<dr; ++i)
        if (abs(Y[i].second - X[mij].first) <= distance)
            aux[++len] = Y[i];

    /// avand un dreptunghi de dimensiuni distance * (2distance) despartit in 2 patrate de dimensiuni
    /// distance*distance pot sa aleg in fiecare patrat maxim 4 puncte care sa fie la distanta cel putin
    /// distance si anume in cele 4 colturi deci in total 8 puncte (in cazul in care pe dreapta care imparte
    /// planul in cele 2 puncte din colturi ar fi de fapt 4.. care sa coincida etc..)
    /// cum eu a aleg un punct i -> mai raman 7 de vazut
    for (i=1; i<=len; ++i)
        for (j=i+1; j<=len && j-i < 8; ++j)
            distance = min(distance, Dist(aux[i], aux[j]));
    return distance;
}

void Write()
{
    FILE *g = fopen("cmap.out", "w");
    fprintf(g, "%.6lf\n", sqrt(1.0*(cmap(0, n))));
    fclose(g);
}

int main()
{
    Read();
    Write();
    return 0;
}