Cod sursa(job #2639355)

Utilizator irimia_alexIrimia Alex irimia_alex Data 1 august 2020 16:05:34
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.18 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#define EPSILON 1e-9
#define INF 1e9

using namespace std;

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

struct point {
	float x, y;
};

vector<point> vec;
point p, q;
float d;

bool cmpX(point& a, point& b) {
	float n = a.x - b.x;
	if (n<EPSILON && n>-EPSILON) return a.y < b.y;
	return a.x < b.x;
}

bool cmpY(point& a, point& b) {
	float n = a.y - b.y;
	if (n<EPSILON && n>-EPSILON) return a.x < b.x;
	return a.y < b.y;
}

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

float bruteForce(vector<point>& strip, float d) {
	float dmin = d;
	for (int i = 0;i < strip.size();++i)
		for (int j = i + 1;j < strip.size() && strip[j].y - strip[i].y < dmin;++j) {
			float tmp = dist(strip[i], strip[j]);
			if (tmp < dmin) dmin = tmp;
		}
	return dmin;
}

void merge(int i, int j, int k, vector<point>& vec) {
	vector<point> res;
	int u = i, v = j + 1;
	while (u <= j && v <= k) {
		if (cmpY(vec[u], vec[j])) {
			res.push_back(vec[u]);
			++u;
		}
		else {
			res.push_back(vec[v]);
			++v;
		}
	}
	while (u <= j) {
		res.push_back(vec[u]);
		++u;
	}
	while (v <= k) {
		res.push_back(vec[v]);
		++v;
	}
	for (u = i;u <= k;++u)
		vec[u] = res[u-i];
}

float closestPairDist(vector<point>& vec, int i, int j,vector<point>& sorted) {
	if (i >= j) {
		if (i == j) sorted[i] = vec[i];
		return INF;
	}
	int m = (i + j) / 2;
	float d1 = closestPairDist(vec, i, m, sorted);
	float d2 = closestPairDist(vec, m + 1, j, sorted);
	float d = min(d1, d2);
	merge(i, m, j, sorted);
	vector<point> strip;
	for (int k = i;k <= j;++k)
		if (abs(vec[k].x - vec[m].x) < d)
			strip.push_back(vec[k]);
	d = bruteForce(strip, d);
	return d;
}

float closestPair(vector<point>& vec) {
	sort(vec.begin(), vec.end(), cmpX);
	vector<point> sorted;
	sorted.resize(vec.size());
	return closestPairDist(vec, 0, vec.size() - 1, sorted);
}

int main() {
	int n;
	fin >> n;
	float x, y;
	while (n--) {
		fin >> x >> y;
		vec.push_back({ x,y });
	}
	fout<<closestPair(vec);
	return 0;
}