Cod sursa(job #864704)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 25 ianuarie 2013 17:38:03
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.25 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];

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, vector<int> &v) {
    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]));

        for(int i = st; i <= dr; i++)
            v.push_back(i);

        for(size_t i = 0; i < v.size(); i++)
            for(size_t j = i + 1; j < v.size(); j++)
                if(P[v[i]].y > P[v[j]].y) {
                    int aux = v[i];
                    v[i] = v[j];
                    v[j] = aux;
                }
        return ret;
    }

    int m = (st + dr) / 2;
    vector<int> v1;
    long long ret1 = minDist(st, m, v1);
    vector<int> v2;
    long long ret2 = minDist(m + 1, dr, v2);

    long long ret = min(ret1, ret2);

    size_t i = 0, j = 0;
    while(i < v1.size() && j < v2.size())
        if(P[v1[i]].y < P[v2[j]].y)
            v.push_back(v1[i++]);
        else
            v.push_back(v2[j++]);
    while(i < v1.size())
        v.push_back(v1[i++]);
    while(j < v2.size())
        v.push_back(v2[j++]);

    for(size_t i = 0; i < v.size(); i++)
        for(size_t j = i + 1; j <= i + 7 && j < v.size(); j++)
            ret = min(ret, dist(P[v[i]], P[v[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);

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

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

	return 0;
}