Cod sursa(job #2491082)

Utilizator Marius2902Chitac Marius Marius2902 Data 11 noiembrie 2019 19:40:47
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;

struct Point {
	int x, y;
	float distance(Point &b)
	{
		return (x - b.x) * (x - b.x) + (y - b.y)*(y - b.y);
	}
};

bool sort_x(Point& a,Point &b)
{
	if (a.x < b.x)
		return true;
	else
		return false;
}


bool sort_y(Point& a, Point &b)
{
	if (a.y < b.y)
		return true;
	else
		return false;
}

float get_min_dist(float d_min, vector<Point> a)
{
	for (int i = 0; i < a.size() - 1; i++)
		for (int j = i + 1; j < a.size() and (a[j].y - a[i].y) < d_min; j++)
			if (a[i].distance(a[j]) < d_min)
				d_min = a[i].distance(a[j]);
	return d_min;
}

float find_closest_points(vector<Point> a, vector<Point> b, int st, int dr)
{
	if (dr - st + 1 <= 3)
	{
		float d_min = a[st].distance(a[st + 1]);
		for (int i = st; i < dr; i++)
			for (int j = i + 1; j <= dr; j++)
				if (a[i].distance(a[j]) < d_min)
					d_min = a[i].distance(a[j]);
		return d_min;
	}
	else
	{
		int mijloc = (st + dr) / 2;
		vector<Point> ord_st, ord_dr;
		for (int i = 0; i < b.size(); i++)
			if (b[i].x <= a[mijloc].x)
				ord_st.push_back(b[i]);
			else
				ord_dr.push_back(b[i]);
		float dist_st = find_closest_points(a, ord_st, st, mijloc);
		float dist_dr = find_closest_points(a, ord_dr, mijloc + 1, dr);
		float d_min = min(dist_st, dist_dr);
		vector<Point> fasie;
		for (int i = 0; i < b.size(); i++)
		{
			if (abs(b[i].x - a[mijloc].x) * abs(b[i].x - a[mijloc].x) < d_min)
				fasie.push_back(b[i]);
		}
		return get_min_dist(d_min, fasie);
	}
	
}

int main()
{
	ifstream in("cmap.in");
	ofstream out("cmap.out");
	int n;
	in >> n;
	vector<Point> X(n), Y(n);
	for (int i = 0; i < n; i++)
	{
		in >> X[i].x >> X[i].y;
		Y[i].x = X[i].x;
		Y[i].y = X[i].y;
	}
	sort(X.begin(), X.end(), sort_x);
	sort(Y.begin(), Y.end(), sort_y);
	out << fixed << setprecision(6) << sqrt(find_closest_points(X, Y, 0, n - 1));
}