Cod sursa(job #2058441)

Utilizator gorneanu.andreiFMI Gorneanu Andrei gorneanu.andrei Data 5 noiembrie 2017 17:27:55
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <vector>
#define inf 9999999
#define MAXN 100500
using namespace std;

struct punct{
    long long x, y;
}a[MAXN], b[MAXN];

int n;

bool cmpX(punct c,punct d){

    return (c.x < d.x);
}

long long dist(punct c,punct d){

    return (c.x - d.x) * (c.x - d.x) + (c.y - d.y) * (c.y - d.y);
}

long long minim(long long a,long long b){

    if(a < b)
        return a;
    return b;
}

long long solve(int st,int dr){

    if(dr - st <= 0)
        return inf;
    else if(dr - st == 1){
        if(a[st].y > a[dr].y)
            swap(a[st],a[dr]);
        return dist(a[st],a[dr]);
    }

    int mid = (st + dr) >> 1;
    long long d = minim(solve(st,mid),solve(mid + 1,dr));

    int b_size = 0;
    int c1 = st, c2 = mid + 1;

    while(c1 <= mid && c2 <= dr){
        if(a[c1].y > a[c2].y){
            b[b_size] = a[c2];
            ++b_size;
            ++c2;
        }
        else{
            b[b_size] = a[c1];
            ++b_size;
            ++c1;
        }
    }

    while(c1 <= mid){
        b[b_size] = a[c1];
        ++b_size;
        ++c1;
    }

    while(c2 <= dr){
        b[b_size] = a[c2];
        ++b_size;
        ++c2;
    }

    for(int i = st;i <= dr; ++i)
        a[i] = b[i - st];

    double d1 = sqrt(d);
    b_size = 0;

    for(int i = st;i <= dr; ++i){
        if(abs(a[mid].x - a[i].x) < d1){
            b[b_size] = a[i];
            ++b_size;
        }
    }

    int j;
    for(int i = 0;i < b_size - 1; ++i)
        for(j = i + 1;j <= i + 7 && j < b_size; ++j)
            d = min(d,dist(b[i],b[j]));

    return d;
}

int main(){

    fstream f("cmap.in",ios::in);
    fstream g("cmap.out",ios::out);

    f >> n;

    for(int i = 0;i < n; ++i)
        f >> a[i].x >> a[i].y;

    sort(a,a + n,cmpX);

    double answ = sqrt(solve(0,n - 1));
    g << fixed << setprecision(6) << answ;

    f.close();
    g.close();
    return 0;
}