Cod sursa(job #1000808)

Utilizator gbi250Gabriela Moldovan gbi250 Data 23 septembrie 2013 19:37:13
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#define x first
#define y second

using namespace std;

typedef pair <int, int> point;

point v[100001];

int n, i;

double dist(point a, point b)
{
    return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}

bool cmp(point a, point b)
{
    return a.y < b.y;
}

double divide(int left, int right)
{
    if(left >= right)
        return 0x3f3f3f3f;
    else if( left + 1 == right )
    {
        if (v[left].y > v[right].y)
            swap(v[left], v[right]);
        return dist(v[left], v[right]);
    }

    int mid = (left + right) >> 1;
    double min_dist = min(divide(left, mid), divide(mid+1, right));
    vector <point> strip;

    for (int i = left; i <= right; ++i)
        if( i!=mid && abs(v[mid].x - v[i].x) < min_dist)
            strip.push_back(v[i]);

    sort(strip.begin(), strip.end(), cmp);

    for (int i = 0; i <strip.size(); ++i)
        for(int j = i+1; j<=i+8 && j<strip.size(); ++j)
            min_dist = min( min_dist, dist(strip[j], strip[i]) );
    return min_dist;
}


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

    scanf("%d", &n);
    for(i=1; i<=n; ++i)
        scanf("%d %d", &v[i].x, &v[i].y);
    sort(v+1, v+n+1);
    double nr=divide(1, n);
    printf("%6lf\n",nr);
    return 0;
}