Cod sursa(job #1831544)

Utilizator botimooMiklos Botond botimoo Data 18 decembrie 2016 11:58:20
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 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;
}

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

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

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

		vector<point> left, right;

		int i = mid;
		while (i >= s && points[mid].x - points[i].x < d){
			left.push_back(points[i]);
			i--;
		}
		sort(left.begin(), left.end(), lessY);

		i = mid + 1;
		while (i <= e && points[i].x - points[mid].x <= d){
			right.push_back(points[i]);
			i++;
		}
		sort(right.begin(), right.end(), lessY);

		if (right.size() > 0 && left.size() > 0){
			i = i;
		}

		return d;
	}
}

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

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

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