Cod sursa(job #1436184)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 15 mai 2015 13:11:54
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#define DIM 100002

using namespace std;

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

pair <int,int> a[DIM];
int Minimum_Square_Distance;
int N;

void scramble(int p,int mid,int u){
    int i=p,j=mid+1,k=0;
    pair <int,int> b[u-p+2];
    while(i<=mid && j<=u)
        if(a[i]<a[j])
            b[++k]=a[i++];
        else
            b[++k]=a[j++];
    for(;i<=mid;i++)
        b[++k]=a[i];
    for(;j<=u;j++)
        b[++k]=a[j];
    for(i=1;i<=k;i++)
        a[p+i-1]=b[i];
}
void mergesort(int p,int u){
    if(p==u)
        return;
    int mid=(p+u)>>1;
    mergesort(p,mid);
    mergesort(mid+1,u);
    scramble(p,mid,u);
}
int squaredist(pair <int,int> p1,pair <int,int> p2){
    return (p2.first-p1.first)*(p2.first-p1.first)+(p2.second-p1.second)*(p2.second-p1.second);
}
int main(){
    fin>>N;
    for(int i=1;i<=N;i++)
        fin>>a[i].first>>a[i].second;
    mergesort(1,N);
    Minimum_Square_Distance=0x3f3f3f3f3f;
    for(int i=2;i<=N;i++)
        Minimum_Square_Distance=min(Minimum_Square_Distance,squaredist(a[i-1],a[i]));
    fout<<setprecision(6)<<fixed<<sqrt(Minimum_Square_Distance)<<"\n";
}