Cod sursa(job #1427129)

Utilizator Miruna_DMiruna Miruna_D Data 1 mai 2015 16:14:33
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <iostream>
#include<fstream>
#include<algorithm>
#include <math.h>
#define Nmax 100001
#define oo 1000000000000000
using namespace std;
  ifstream fin("cmap.in");
  ofstream fout("cmap.out");
  int n,Lenght,nr=0;

struct point
{
    long long int  x,y;
};

point v[Nmax],Y[Nmax], sir[Nmax],aux[Nmax];

long long distance(point p1, point p2)
{
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}


bool cmp1(point p1, point p2)
{
    return p1.x<p2.x;
}

void Swap(point p1, point p2)
{
    swap(p1.x,p2.x);
    swap(p1.y,p2.y);
}
void Interclasare(long long int st,long long int m,long long int dr)
{
long long int i,j;

 i=st;
 j=m+1;


    while(i<=m&&j<=dr)
        if(Y[i].y<Y[j].y) aux[++nr]=Y[i++];
        else                  aux[++nr]=Y[j++];

    while(i<=m) aux[++nr]=Y[i++];
    while(j<=dr) aux[++nr]=Y[j++];

    for(i=st;i<=dr;i++) Y[i]=aux[i];

}
long long DivideImpera(int st,int dr)
{
    int i,j;

    if(st>=dr)
        return oo;
    long long DMIN=oo;
    if(dr-st<=2)
    {
        for(i=st;i<=dr;i++)
            Y[i]=v[i];
        for(i=st;i<dr;i++)
            for(j=i+1;j<=dr;j++)
            if(Y[i].y>Y[i].y) Swap(Y[i],Y[j]);


        for(i=st;i<dr;i++)
            for(j=i+1;j<=dr;j++)
                DMIN=min(distance(v[i],v[j]),DMIN);

        return DMIN;

    }

    int m=(st+dr)/2;
    int mij=v[m].x;
    long long d1=DivideImpera(st,m);
    long long d2=DivideImpera(m+1,dr);
    DMIN=min(d1,d2);

    Interclasare(st,m,dr);

    for(i=st;i<=dr;i++)
        if(abs(Y[i].x-Y[m].x)<=DMIN) sir[++Lenght]=Y[i];



    for(i=1;i<=Lenght;i++)
        for(j=1;j<=7 && i+j<=Lenght;j++)
            DMIN=min(distance(sir[i],sir[i+j]),DMIN)

    return DMIN;
}


int main()
{
    fin>>n;
    int i;
    for(i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;

    sort(v+1,v+n+1,cmp1);

    DMIN=DivideImpera(1,n);

    fout<<fixed<<setprecision(6)<<DMIN;


    return 0;
}