Cod sursa(job #2064852)

Utilizator Eduard6421Eduard Gabriel Eduard6421 Data 12 noiembrie 2017 22:23:58
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.34 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 :
    double x,y;



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


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

        return sqrt(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;

    }

}


double small_dist(int left,int right)
{

    int i,j;
    double dist = INF;

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

    return dist;
}


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


    int m = (left + right ) / 2;

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

    double d = min(d1,d2);

    int k = 0;

    for(int i = left ; i<=right ; ++i)
    {
        if(point_distance(v_sortedx[i],v_sortedx[m]) < 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)
        {
            double 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,mycompx);
    sort(v_sortedy+1,v_sortedy+n,mycompy);

    out<<setprecision(8)<<min_distance(1,n);


    return 0;


}