Cod sursa(job #2174137)

Utilizator maria_sinteaMaria Sintea maria_sintea Data 16 martie 2018 10:54:50
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#define N 100005

using namespace std;

struct punct
{
    int x, y;
}v[N], a[N];
int n;
long long dmax, INF;

void citire()
{
    scanf("%d\n", &n);
    for(int i=0;i<n;i++)
        scanf("%d %d\n", &v[i].x, &v[i].y);
}

long long dist(punct e, punct f)
{
    return 1LL*(e.x-f.x)*(e.x-f.x)+1LL*(e.y-f.y)*(e.y-f.y);
}

int cmp(punct e, punct f)
{
    return (e.x<f.x || e.x==f.x && e.y<f.y);
}

void interclasare(int st, int mij, int dr)
{
    int k=-1, i, j;
    for(i=st, j=mij+1;i<=mij && j<=dr;)
        if(cmp(v[i], v[j]))
            a[++k]=v[i++];
        else
            a[++k]=v[j++];
    while(i<=mij)
        a[++k]=v[i++];
    while(j<=dr)
        a[++k]=v[j++];
    for(i=dr;i>=st;i--, k--)
        v[i]=a[k];
}

long long divide(int st, int dr)
{
    int nr=0;
    long long min=INF;
    if(dr-st<3)
    {
        for(int i=st;i<dr;i++)
            for(int j=i+1;j<=dr;j++)
            {
                long long d=dist(v[i], v[j]);
                if(min>d)
                    min=d;
            }
        sort(v+st, v+dr+1, cmp);
        return min;
    }
    int mij=(st+dr)/2;
    long long d1=divide(st, mij);
    long long d2=divide(mij+1, dr);
    if(d1>d2)
        d1=d2;
    min=d1;
    interclasare(st, mij, dr);
    for(int i=st;i<=dr;i++)
        if(dist(v[i], v[mij])<=d1)
            a[nr++]=v[i];
    for(int i=0;i<nr;i++)
        for(int j=i+1;j<nr && j<=i+7;j++)
        {
            long long d=dist(a[i], a[j]);
            if(d<min)
                min=d;
        }
    return min;
}

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

    citire();
    INF=dist(v[0], v[1]);
    sort(v, v+n, cmp);
    dmax=divide(0, n-1);
    printf("%.6llf\n", sqrt(dmax));
    return 0;
}