Cod sursa(job #864884)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 25 ianuarie 2013 20:36:49
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
#include <cstdio>
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <cstring>
#include <ctime>
#include <cassert>
#include <utility>

using namespace std;

#define x first
#define y second

#define MAXN 100005
#define INF 1e18
typedef pair<int, int> Point;

int N;
Point P[MAXN], Y[MAXN], AUX[MAXN], Z[MAXN];

bool cmp(const Point &a, const Point &b) {
    return a.y < b.y || (a.y == b.y && a.x < b.x);
}

inline long long dist(const Point &a, const Point &b) {
    return (long long)(a.x - b.x) * (a.x - b.x) + (long long)(a.y - b.y) * (a.y - b.y);
}

long long minDist(int st, int dr) {
    if(dr - st + 1 <= 1)
        return INF;
    if(dr - st + 1 <= 2) {
        if(!cmp(Y[st], Y[st + 1]))
            swap(Y[st], Y[st + 1]);

        return dist(P[st], P[st + 1]);
    }

    int m = (st + dr) / 2;

    long long ret = min(minDist(st, m), minDist(m + 1, dr));

    int i, j, k;

    i = st;
    while(i <= m) {
        AUX[i] = Y[i];
        i++;
    }

    j = st;
    k = st;
    while(i <= dr && j <= m) {
        if(cmp(Y[i], AUX[j]))
            Y[k++] = Y[i++];
        else
            Y[k++] = AUX[j++];
    }
    while(i <= dr)
        Y[k++] = Y[i++];
    while(j <= m)
        Y[k++] = AUX[j++];

/*
    merge(Y + st, Y + m + 1, Y + m + 1, Y + dr + 1, AUX + st, cmp);
    copy(AUX + st, AUX + dr + 1, Y + st);
*/

    k = 0;
    for(int i = st; i <= dr; i++)
        if((long long)(Y[i].x - P[m + 1].x) * (Y[i].x - P[m + 1].x) <= ret)
            AUX[k++] = Y[i];

    for(int i = 0; i < k - 1; i++)
        for(int j = i + 1; j <= i + 7 && j < k; j++)
            ret = min(ret, dist(AUX[i], AUX[j]));

    return ret;
}

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

    scanf("%d", &N);
    for(int i = 0; i < N; i++)
        scanf("%d %d", &P[i].x, &P[i].y);

    sort(P, P + N);
    for(int i = 0; i < N; i++)
        Y[i] = P[i];

    vector<int> v;
    double ans = sqrt(minDist(0, N - 1));

    printf("%.6lf\n", ans);

	return 0;
}