Cod sursa(job #2070843)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 19 noiembrie 2017 22:49:18
Problema Cele mai apropiate puncte din plan Scor 75
Compilator cpp Status done
Runda Arhiva educationala Marime 2.23 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#define X first
#define Y second
#define NMAX 100001

using namespace std;

typedef long long ll;
typedef pair < ll, ll > point;
point points[NMAX], strip[NMAX];
int n, n_strip;

void read() {

	ifstream in("cmap.in");
	ll x, y;
	in >> n;
	for (int i = 1; i <= n; ++i) {

		in >> x >> y;
		points[i] = make_pair(x, y);
	}
	in.close();
}

bool compareX(const point& f, const point& s) {

	if ((f.X < s.X) || (f.X == s.X && f.Y < s.Y))
		return true;
	return false;
}

bool compareY(const point& f, const point& s) {

	if ((f.Y < s.Y) || (f.Y == s.Y && f.X < s.X))
		return true;
	return false;
}

inline ll dist(const point& p1, const point& p2) {

	return (p1.X - p2.X) * (p1.X - p2.X) + (p1.Y - p2.Y) * (p1.Y - p2.Y);
}

ll brute_dist(int left, int right) {

	ll best_dist = 0;
	for (int i = left; i < right; i++)
		for (int j = i + 1; j <= right; j++) {

			if (best_dist == 0)
				best_dist = dist(points[i], points[j]);
			else if (best_dist > dist(points[i], points[j]))
				best_dist = dist(points[i], points[j]);
		}
	return best_dist;
}

ll min_dist_strip(ll d_min) {

	ll best_dist = d_min;

	sort(strip, strip + n_strip + 1, compareY);
	for (int i = 1; i < n_strip; i++)
		for (int j = i + 1, k = 1; k <= 7 && j <= n_strip; j++, k++)
			best_dist = min(best_dist, dist(strip[i], strip[j]));

	return best_dist;
}

ll min_dist(int left, int right) {
	
	if (right - left < 4)
		return brute_dist(left, right);
	else {

		int mid = left + (right - left) / 2;
		ll d1 = min_dist(left, mid);
		ll d2 = min_dist(mid + 1, right);
		ll d = min(d1, d2);

		n_strip = 0;

		for (int i = mid; i >= left; --i)
			if (points[mid].X - points[i].X < d)
				strip[++n_strip] = points[i];

		for (int i = mid + 1; i <= right; i++)
			if (points[i].X - points[mid].X < d)
				strip[++n_strip] = points[i];

		ll d3 = min_dist_strip(d);

		return min(d, d3);
	}
	return 0;
}

int main() {

	read();
	sort(points, points + n + 1, compareX);

	ofstream out("cmap.out");
	out << fixed << setprecision(6) << sqrt(min_dist(1, n)) << "\n";
	
	out.close();
	return 0;
}