Cod sursa(job #864720)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 25 ianuarie 2013 17:58:23
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 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 1e17
typedef pair<int, int> Point;

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

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 <= 3) {
        long long ret = INF;
        for(int i = st; i < dr; i++)
            for(int j = i + 1; j <= dr; j++) {
                ret = min(ret, dist(P[i], P[j]));
                if(Y[i].y > Y[j].y)
                    swap(Y[i], Y[j]);
            }

        return ret;
    }

    int m = (st + dr) / 2;
    long long ret1 = minDist(st, m);
    long long ret2 = minDist(m + 1, dr);

    long long ret = min(ret1, ret2);

    int i, j, k;

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

    j = k = st;
    while(i <= dr && j < i) {
        if(Y[i].y < AUX[j].y)
            Y[k++] = Y[i++];
        else
            Y[k++] = AUX[j++];
    }
    while(j < i)
        Y[k++] = AUX[j++];
    while(i <= dr)
        Y[k++] = Y[i++];
    //merge(Y + st, Y + m + 1, Y + m + 1, Y + dr + 1, Y + st);

    for(int i = st; i <= dr; i++)
        for(int j = i + 1; j <= i + 7 && j <= dr; j++)
            ret = min(ret, dist(Y[i], Y[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;
}