Cod sursa(job #1226196)

Utilizator SteveStefan Eniceicu Steve Data 4 septembrie 2014 18:56:59
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.16 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
#define INF 1LL * 1000000000 * 1000000000
using namespace std;

typedef struct {
    int x;
    int y;
} punct;

int N;
punct v[100011];
punct V[100011];
vector <int> indici;

inline int cmp1 (punct a, punct b) {
    if (a.x == b.x) return (a.y < b.y);
    return (a.x < b.x);
}

inline int cmp2 (punct a, punct b) {
    if (a.y == b.y) return (a.x < b.x);
    return (a.y < b.y);
}

void Citire () {
    ifstream fin ("cmap.in");
    fin >> N;
    for (int i = 1; i <= N; i++)
        fin >> v[i].x >> v[i].y;
    fin.close ();
}

long long min (long long A, long long B) {
    if (A < B) return A;
    return B;
}

long long dist (int i, int j) {
    return (1LL * (v[i].x - v[j].x) * (v[i].x - v[j].x) + 1LL * (v[i].y - v[j].y) * (v[i].y - v[j].y));
}

inline int abs (int a) {
    if (a >= 0) return a;
    return -a;
}

void mergem (int L, int R) {
    int mijl = (L + R) / 2;
    int i = L;
    int j = mijl + 1;
    for (; i <= mijl && j <= R;)
    {
        if (cmp2 (v[i], v[j])) V[i + j - mijl - 1] = v[i], i++;
        else V[i + j - mijl - 1] = v[j], j++;
    }
    for (; i <= mijl; i++)
        V[i + j - mijl - 1] = v[i];
    for (; j <= R; j++)
        V[i + j - mijl - 1] = v[j];
    for (int i = L; i <= R; i++)
        v[i] = V[i];
}

long long DivQ (int L, int R) {
    if (L >= R) return INF;
    int mijl = (L + R) / 2;
    long long D = min (DivQ (L, mijl), DivQ (mijl + 1, R));
    if (R == L + 1) sort (v + L, v + R + 1, cmp2);
    else mergem (L, R);
    for (int i = L; i <= R; i++)
        if (abs (v[i].x - v[mijl].x) <= D) indici.push_back (i);
    for (int i = 0; i < (int) indici.size (); i++)
        for (int j = i + 1; j <= i + 7 && j < (int) indici.size (); j++)
            D = min (D, dist (indici[i], indici[j]));
    indici.clear ();
    return D;
}

void Scriere () {
    ofstream fout ("cmap.out");
    fout << fixed << setprecision (6) << sqrt (1.0 * DivQ (1, N));
    fout.close ();
}

int main () {
    Citire ();
    sort (v + 1, v + N + 1, cmp1);
    Scriere ();
    return 0;
}