Cod sursa(job #2072647)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 22 noiembrie 2017 00:30:13
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 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(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;
}