Cod sursa(job #1584114)

Utilizator metrix007Lungu Ioan Adrian metrix007 Data 29 ianuarie 2016 18:32:23
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define NMAX 100002
#define INF 2000000001
using namespace std;

struct punct
{
    long long x,y;
}X[NMAX],Y[NMAX],A;

bool compX(punct a,punct b)
{
    if(a.x<b.x)
        return true;
    if(a.x>b.x)
        return false;
    else
    {
        if(a.y<b.y)
            return true;
        else return false;
    }
}

bool compY(punct a,punct b)
{
    if(a.y<b.y)
        return true;
    else
        return false;
}

int n;

double distanta(punct a,punct b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double divide(int st,int dr)
{
   double dist,minim,m;
    if(dr-st+1<=3)
    {
        dist = INF;

        for(int i=st;i<=dr;i++)
        {
            for(int j=i+1;j<=dr;j++)
                dist = min(distanta(X[i],X[j]),dist);
        }
        sort(Y+st,Y+dr+1,compY);
        return dist;
    }
    else
    {
        int mij = (st+dr)/2;
        minim = min(divide(st,mij),divide(mij+1,dr));

        punct temp[dr-st+2];
        merge(Y+st,Y+mij+1,Y+mij+1,Y+dr+1,temp+1,compY);
        copy(temp+1,temp+dr-st+2,Y+st);

        for(int i=st;i<=dr;i++)
        {
            for(int j=1;j<=7 && i+j<=dr &&  Y[i+j].y-Y[i].y<=minim;j++)
            {
                minim = min(minim,distanta(Y[i],Y[i+j]));
            }
        }
        return minim;
    }
}


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


int main()
{
    in >> n;
    for(int i=1;i<=n;i++)
    {
        in >> A.x >> A.y;
        X[i] = A; Y[i] = A;
    }
    sort(X+1,X+n+1,compX);
    out << fixed << setprecision(6) << divide(1,n);



    return 0;
}