Cod sursa(job #1681539)

Utilizator razvandRazvan Dumitru razvand Data 9 aprilie 2016 15:59:21
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 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];
vector<pct> tmp;
vector<pct>::iterator it;
vector<pct>::iterator it2;

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;
    tmp.clear();

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

    sort(tmp.begin(), tmp.end(), cmp2);

    for(it = tmp.begin(); it != tmp.end(); it++)
        for(it2 = it+1; it2 != tmp.end(); it2++)
            minX = min(minX, distP(*it, *it2));

    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;
}