Cod sursa(job #1503265)

Utilizator stefanzzzStefan Popa stefanzzz Data 15 octombrie 2015 20:07:04
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define Point pair<int, int>
#define x first
#define y second
#define mp make_pair
#define MAXN 100005
#define INF 0x7fffffffffffffff
#define MIN(a, b) (((a) < (b))?(a):(b))
using namespace std;

int n;
Point v[MAXN];

inline long long dist(Point A, Point B) {
    long long dx = A.x - B.x;
    long long dy = A.y - B.y;
    return dx * dx + dy * dy;
}

bool Comp(Point a, Point b) {
    return a.second < b.second;
}

long long solve(int l, int r) {
    if(r - l + 1 <= 3) {
        long long ans = INF;
        for(int i = l; i < r; i++)
            for(int j = i + 1; j <= r; j++) {
                long long d = dist(v[l], v[r]);
                ans = MIN(ans, d);
            }
        return ans;
    }

    int mid = (l + r) >> 1;
    long long d1 = solve(l, mid);
    long long d2 = solve(mid + 1, r);

    long long ans = MIN(d1, d2);

    int xx = v[mid].x;
    vector<Point> a;
    for(int i = l; i <= r; i++)
        if(v[i].x > xx - sqrt(ans) - 1 && v[i].x < xx + sqrt(ans) + 1)
            a.push_back(v[i]);

    sort(a.begin(), a.end(), Comp);
    for(int i = 0; i < a.size(); i++)
        for(int j = i + 1; j < a.size() && j - i <= 7; j++) {
            long long d = dist(a[i], a[j]);
            ans = MIN(ans, d);
        }
    return ans;
}

int main()
{
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);

    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d %d", &v[i].x, &v[i].y);

    sort(v + 1, v + n + 1);
    printf("%.15f\n", sqrt(solve(1, n)));

    return 0;
}