Cod sursa(job #2489183)

Utilizator irares27Rares Munteanu irares27 Data 7 noiembrie 2019 23:53:36
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.44 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <float.h>
#include <iomanip>
#include <cmath>

using namespace std;

ifstream f("cmap.in");
ofstream g("cmap.out");


struct point
{
	double x, y;
	friend istream &operator >>(istream& in, point &a)
	{
		in >> a.x >> a.y;
		return in;
	}

	friend ostream &operator <<(ostream& out, const point &a)
	{
		out << a.x << " " << a.y << "\n";
		return out;
	}

	friend double dist_sq(const point& a, const point& b)
	{
		double first = (a.x - b.x) * (a.x - b.x);
		double second = (a.y - b.y) * (a.y - b.y);
		return double(first + second);
	}
	friend double dist(const point& a, const point& b)
	{
		return double(sqrt(dist_sq(a,b)));
	}
};

int read(point * &v, ifstream &f)
{
	int n;
	point temp;
	f >> n;
	v = new point[n];
	for (int i = 0; i < n; i++)
	{
		f >> temp;
		v[i] = temp;
	}
	return n;
}

void afis(point *v, int size)
{
	for (int i = 0; i < size; i++)
		cout << v[i].x << " " << v[i].y << "\n";
	cout << "\n";
}

bool comp_x(const point& a, const point& b)
{
	return a.x < b.x;
}
bool comp_y(const point& a, const point& b)
{
	return a.y < b.y;
}


double bruteForce(point* vp, int n)
{
	double min = FLT_MAX;
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			if (dist(vp[i], vp[j]) < min)
				min = dist(vp[i], vp[j]);
	return min;
}

double min(double x, double y)
{
	return (x < y) ? x : y;
}

double stripClosest(point* strip, int size, double d)
{
	double min = d;
	sort(strip,strip+size, comp_y);

	for (int i = 0; i < size; ++i)
		for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < min; ++j)
			if (dist(strip[i], strip[j]) < min)
				min = dist(strip[i], strip[j]);

	return min;

}

double closestDivide(point *vp, int n)
{
	if (n <= 3)
		return bruteForce(vp, n);

	int mid = n / 2;
	point midp = vp[mid];

	double minleft = closestDivide(vp, mid);
	double minright = closestDivide(vp + mid, n - mid);

	double d = min(minleft, minright);

	point* strip = new point[n];

	int j = 0;
	for (int i = 0; i < n; i++)
		if (abs(vp[i].x - midp.x) < d)
			strip[j] = vp[i], j++;

	return min(d, stripClosest(strip, j, d));
}

double closest(point *vp, int n)
{
	sort(vp,vp+n,comp_x);
	return closestDivide(vp, n);
}


int main()
{
	int n;
	point* v=new point[0];
	n = read(v, f);
	g<<setprecision(8)<<closest(v, n);

	delete[]v;
}