Cod sursa(job #2068623)

Utilizator Julian.FMI Caluian Iulian Julian. Data 18 noiembrie 2017 10:02:06
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;
#define nmax 100099
struct punct{
double x,y;
};

punct p[nmax],aux[nmax];

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



double minDist(int st,int dr){
    if(dr-st+1 ==3){
        if(p[st].y > p[st+1].y)swap(p[st],p[st+1]);
        if(p[st+1].y > p[st+2].y)swap(p[st+1],p[st+2]);
        if(p[st].y > p[st+1].y)swap(p[st],p[st+1]);

        return min(dist(p[st],p[st+1]),min(dist(p[st+1],p[st+2]),dist(p[st],p[st+2])));
    }if(dr-st+1 ==2){
        if(p[st].y>p[st+1].y)swap(p[st],p[st+1]);
        return dist(p[st],p[st+1]);


    }else{
    //Mai mult de 3 elemente:
    int mid = (st+dr)/2;
    double delta = min(minDist(st,mid),minDist(mid+1,dr));

    //Interclasam:
    int i,j,k; i=k=st; j=mid+1;
    while(i<=mid && j<=dr){
        if(p[i].y < p[j].y)aux[k++]=p[i++];
            else aux[k++]=p[j++];
    }
    while(i<=mid)aux[k++]=p[i++];
    while(j<=dr) aux[k++]=p[j++];

    for(i=st;i<=dr;i++)p[i]=aux[i];
    for(i=st;i<=dr;i++)
    {    j= min(dr,i+7);
            for(k=i+1;k<=j;k++)
                delta= min(delta,dist(p[i],p[k]));
    }
    return delta;
    }


}


int main(){
    ifstream cin("cmap.in");
    ofstream cout("cmap.out");
    int n,i;
    cin>>n;
    for(i=1;i<=n;i++)cin>>p[i].x>>p[i].y;
    cout<<sqrt(minDist(1,n));

}