Cod sursa(job #2064872)

Utilizator Eduard6421Eduard Gabriel Eduard6421 Data 12 noiembrie 2017 22:56:54
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.44 kb
#include<algorithm>
#include<vector>
#include<fstream>
#include<iostream>
#include<cstdio>
#include<iomanip>.
#include<cmath>

#define NMAX 100000 + 5
#define INF 0xFFFFFFFFFFFFF

#define min(a,b) a < b ? a : b

using namespace std;

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

class POINT
{
public :
    long long  x,y;



friend bool mycompx(POINT a,POINT b);
friend bool mycompy(POINT a,POINT b);


friend long long  point_distance(POINT a, POINT b)
    {
        long long  lat_1 = b.x - a.x;
        long long  lat_2 = b.y - a.y;

        return lat_1*lat_1 + lat_2*lat_2;
    }


};

bool mycompy(POINT a,POINT b)
    {
        return a.y < b.y;
    }


bool mycompx(POINT a,POINT b)
    {
        return a.x < b.x;
    }



POINT v_sortedx[NMAX];
POINT v_sortedy[NMAX];
POINT strip[NMAX];


int n;

void read_data()
{
    in >> n;

    for(int i = 1 ; i<=n ; ++i)
    {
        in>>v_sortedx[i].x;
        in>>v_sortedx[i].y;

        v_sortedy[i].x = v_sortedx[i].x;
        v_sortedy[i].y = v_sortedx[i].y;

    }

}


long long  small_dist(int left,int right)
{

    int i,j;
    long long  dist = INF;

    for(i = left ; i < right ; ++i)
        for( j = i+1 ; j <=right ; ++j)
        {
            long long  temp = point_distance(v_sortedx[i],v_sortedx[j]);
            if( temp < dist)
                dist = temp;
        }

    return dist;
}


long long  min_distance(int left,int right)
{
    if(right - left <= 4)
    {
        return small_dist(left,right);
    }


    int m = (left + right ) / 2;

    long long  d1 = min_distance(left,m);
    long long  d2 = min_distance(m,right);

    long long  d = min(d1,d2);

    int k = 0;

    for(int i = left ; i<=right ; ++i)
    {
        if(point_distance(v_sortedx[i],v_sortedx[m]) < d*d)
            strip[++k] = v_sortedx[i];
    }

    sort(strip+1,strip+k+1,mycompy);

    for(int i = 1 ; i<=k ; ++i)
    {

        for(int j = i + 1; i-j <= 7 && j <=k ; ++j)
        {
            long long  dist = point_distance(strip[i],strip[j]);
            if(dist < d)
                d = dist;
        }
    }

    return d;
}




int main()
{
    read_data();


    sort(v_sortedx+1,v_sortedx+n+1,mycompx);
    sort(v_sortedy+1,v_sortedy+n+1,mycompy);

    long long  d;

    d = min_distance(1,n);


    out<<fixed<<setprecision(6)<<sqrt(d);

    return 0;


}