Cod sursa(job #1681544)

Utilizator razvandRazvan Dumitru razvand Data 9 aprilie 2016 16:03:37
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <limits.h>
#include <cmath>
#include <iomanip>

using namespace std;

struct pct {
    long long x;
    long long y;
};

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

long long dist;
pct v[100003];
pct v2[100003];

bool cmp(pct a, pct b) {
    if(a.x != b.x)
        return a.x < b.x;
    else
        return a.y < b.y;
}

bool cmp2(pct a, pct b) {
    if(a.y != b.y)
        return a.y < b.y;
    else
        return a.x < b.x;
}

inline long long distP(pct a, pct b) {
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

long long sm(int st, int dr) {

    if(dr == st+1)
        return distP(v[st], v[dr]);

    int mid = (st+dr)/2;
    long long minX = min(sm(st, mid), sm(mid, dr));
    int line = (v[st].x+v[dr].x)/2;
    int k = 0;

    for(int i = st; i <= dr; i++)
        if(abs(v[i].x-line) < minX)
            v2[k++] = v[i];

    sort(v2, v2+k, cmp2);

    for(int i = 0; i < k; i++)
        for(int j = i+1; j < k && j-i < 8; j++)
            minX = min(minX, distP(v2[i], v2[j]));

    return minX;

}

int main() {

    int n;
    in >> n;

    for(int i = 1; i <= n; i++)
        in >> v[i].x >> v[i].y;
    sort(v, v+n, cmp);

    out << fixed << setprecision(6) << sqrt(sm(1, n));

    return 0;
}