Cod sursa(job #864699)

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

int N;
Point P[MAXN];

double dist(const Point &a, const Point &b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

double minDist(int st, int dr, vector<int> &v) {
    if(dr - st + 1 <= 3) {
        double 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;
    double ret1 = minDist(st, m, v1);
    vector<int> v2;
    double ret2 = minDist(m + 1, dr, v2);

    double 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 = minDist(0, N - 1, v);

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

	return 0;
}