Cod sursa(job #1439453)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 22 mai 2015 12:55:44
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#include <climits>
#include <algorithm>
#define lint long long
#define DIM 100002

using namespace std;

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

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

void scramble(int p,int mid,int u){
    int i=p,j=mid+1,k=0;
    pair <lint,lint> 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);
}
lint squaredist(pair <lint,lint> p1,pair <lint,lint> p2){
    return 1LL*(p2.first-p1.first)*(p2.first-p1.first)+1LL*(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);
    sort(a+1,a+N+1);
    Minimum_Square_Distance=LLONG_MAX;
    for(int i=1;i<N;i++)
        for(int j=i+1;j<=N && a[j].first-a[i].first < Minimum_Square_Distance;j++)
            if(abs(a[j].second-a[i].second)<Minimum_Square_Distance)
                Minimum_Square_Distance=min(Minimum_Square_Distance,squaredist(a[i-1],a[i]));
    fout<<setprecision(6)<<fixed<<sqrt(Minimum_Square_Distance)<<"\n";
}