Cod sursa(job #2070965)

Utilizator lilosanduNicu Andrei lilosandu Data 20 noiembrie 2017 03:27:35
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

ifstream f("cmap.in");
ofstream g("cmap.out");

#define maxim 100000

struct punct
{
    int x,y;
}v[maxim],v2[maxim];

int n;

bool sortare_x (punct a,punct b)
{
    return a.x<b.x;
}

bool sortare_y(punct a,punct b)
{
    return a.y<b.y;
}

long long distanta ( punct a,punct b)
{
    long long ecx=1LL * (a.x-b.x );
    long long ecy=1LL * ( a.y-b.y );

    return  ecx*ecx+ecy*ecy ;
}


long long div_imp ( int st, int dr)
{
    if( dr-st == 1)
        return distanta(v[st],v[dr]);

    if ( dr-st==2 )
        return min(distanta(v[st],v[st+1]),min(distanta(v[st+1], v[dr]),distanta(v[st], v[dr])));

    int mij=( st + dr )/2;
    long long dist1=div_imp(st,mij) ;
    long long dist2=div_imp(mij+1,dr) ;

    long long dmin=min(dist1,dist2);
    long long delta=ceil(sqrt(dmin));   ///ca sa compar cu int

    int i,j,k=0;
    for(i=st; i<=dr;i++)
    {
        if(abs(v[i].x-v[mij].x )<=delta)
        {
            v2[k].x=v[i].x;
            v2[k].y=v[i].y;
            k++;
        }
    }

    sort(v2,v2+k,sortare_y);

    for(i=0;i<k;i++)
        for(j=i+1;j<=(i+7)&&j<k;j++)
        {
            dmin=min(dmin,distanta(v2[i],v2[j]));
        }
    return dmin;
}

int main()
{
    int n;
    f>>n;

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

    sort(v,v+n,sortare_x);

    g <<fixed<<setprecision(6)<<sqrt(div_imp(0,n-1));
    return 0;
}