Mai intai trebuie sa te autentifici.
Cod sursa(job #2072646)
Utilizator | Data | 22 noiembrie 2017 00:28:45 | |
---|---|---|---|
Problema | Cele mai apropiate puncte din plan | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.26 kb |
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <climits>
#include <math.h>
using namespace std;
int n ;
long long *holder;
vector< pair<long long,long long> > v;
long long dist(const pair<long long,long long> &a, const pair<long long,long long> &b){
long long x = a.first - b.first;
long long y = a.second - b.second;
return x*x + y*y;
}
void build(int index,int left,int right){
if( left == right){
return;
}
if( right - left == 1){
holder[index] = dist( v[left] , v[right] );
return ;
}
int m = (left + right) >> 1;
build(2*index , left , m);
build(2*index+1, m+1 , right);
holder[index] = min(holder[2*index] , holder[2*index+1] );
holder[index] = min(holder[index] , dist( v[m] , v[m+1] ));
}
int main(){
ifstream f("cmap.in", std::ifstream::in);
f >> n;
holder = new long long[2*n + 5];
for(int i=1;i<=2*n;++i)
holder[i] = LLONG_MAX;
v.push_back(make_pair<long long,long long>(0,0));
for(int i=1; i <= n; ++i){
long long x,y; f>>x>>y;
v.push_back(make_pair<long long,long long>(x,y));
}
sort (v.begin(), v.end() );
build(1 , 1 , n);
ofstream g("cmap.out", std::ifstream::out);
g << sqrt(holder[1]);
printf("%f\n",sqrt(holder[1]) );
delete[] holder;
return 0;
}