Cod sursa(job #2089078)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 16 decembrie 2017 10:47:28
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#define NMAX 100005
#define ll long long
#define INF 0x3f3f3f3f

using namespace std;

int n;
pair <int, int> p[NMAX], v[NMAX];
ll minim;

ll distantaPuncte2(pair<int, int> a, pair<int, int> b)
{
    ll x = (a.first - b.first) * 1LL;
    ll y = (a.second - b.second) * 1LL;
    return x * x + y * y;
}

bool cmp(pair<int, int> a, pair<int, int> b)
{
    if(a.first < b.first || (a.first == b.first && a.second < b.second))
        return true;
    return false;
}

void read()
{
    scanf("%d", &n);
    for(int i=1; i<=n; ++i)
        scanf("%d %d", &p[i].first, &p[i].second);
    sort(p+1, p + n + 1);
}

ll solveBrut(int left, int right)
{
    ll minimAux = INF;
    for(int i = left; i < right; ++i)
        for(int j = i + 1; j <= right; ++j)
            minimAux = min(minimAux, distantaPuncte2(p[i], p[j]));
    return minimAux;
}

void mergeSort(int l, int m, int r)
{
    int k = 0, i, j;
    for(i = l, j = m + 1; i <= m && j <= r; )
        if(cmp(p[i], p[j]) == true)
            v[++k] = p[i++];
        else
            v[++k] = p[j++];
    while(i <= m)
        v[++k] = p[i++];
    while(j <= r)
        v[++k] = p[j++];

    for(j = r; j >= l; --j)
        p[j] = v[k--];
}

ll solve(int l, int r)
{
    if(r - l < 3)
        return solveBrut(l, r);

    int mijloc = (r + l)/2;
    ll d1 = solve(1, mijloc), d2 = solve(mijloc + 1, r);
    minim = min(d1, d2);

    mergeSort(l, mijloc, r);

    int k = 0;

    for(int i = l; i <= r; ++i)
        if((p[i].first - p[mijloc].first) * (p[i].first - p[mijloc].first) < minim)
            v[++k] = p[i];
    for(int i = 1; i < k; ++i)
        for(int j = i+1; j <= i+7 && j <= k; ++j)
            minim = min(minim, distantaPuncte2(v[i], v[j]));
    return minim;
}

int main()
{
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);
    read();
    printf("%.6lf", sqrt(solve(1, n)));
    return 0;
}