Cod sursa(job #1831528)

Utilizator botimooMiklos Botond botimoo Data 18 decembrie 2016 11:37:10
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

struct point{
	int x, y;
};

int n;
vector<point> points;
vector<point> points2;

void in(){
	ifstream fin("cmap.in");
	fin >> n;
	for (int i = 0; i < n; i++)
	{
		point p;
		fin >> p.x >> p.y;
		points.push_back(p);
	}
}

bool lessX(point a, point b){
	return a.x < b.x;
}

bool lessY(point a, point b){
	return a.y < b.y;
}

double dist(point a, point b){
	return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

double minDist(int & s, int & e){
	if (e - s == 1){
		//2 points
		return dist(points[s], points[e]);
	}
	else if (e - s == 2){
		//3 points
		double d12 = dist(points[s], points[s + 1]);
		double d23 = dist(points[s + 1], points[e]);
		double d13 = dist(points[s], points[e]);

		double d = min(d12, min(d23, d13));
		if (d == d12){
			e = s + 1;
		}
		else if (d == d23)
		{
			s = s + 1;
		}
		return d;
	}
	else{
		int mid = (e + s) / 2;
		int mid2 = mid + 1;

		double d1 = minDist(s, mid);
		double d2 = minDist(mid2, e);

		if (d1 < d2){
			e = mid;
		}
		else s = mid2;
		return min(d1, d2);

	}
}

int main(){
	in();
	points2 = points;
	sort(points.begin(), points.end(), lessX);

	int a = 0, b = n-1;
	double d = minDist(a, b);

	ofstream f("cmap.out");
	f << fixed << setprecision(6) << d;
	return 0;
}