Cod sursa(job #1443906)

Utilizator MarianVasilcaMarian Vasilca MarianVasilca Data 28 mai 2015 23:32:52
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 3.01 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <cmath>

#define int64 long long
#define uint64 unsigned long long

const char *in_file_name = "cmap.in";
const char *out_file_name = "cmap.out";
const uint64 inf = (1ULL << 63) - 1ULL;
const int64 MAX_N = 100005;

using namespace std;

ifstream in_file;
ofstream out_file;

int N;
vector< pair<int64, int64> > points;
vector < pair<int64, int64> > v_points;
vector < pair<int64, int64> > V(MAX_N);

void die(bool assertion, const char *message)
{
	if (assertion) {
		fprintf(stderr, "(%s, %d): ",__FILE__, __LINE__);
		perror(message);
		exit(EXIT_FAILURE);
	}
}

int64 distance(int64 ax, int64 ay, int64 bx, int64 by)
{
	int64 result = 1LL * (int64)((ax - bx) * (ax - bx) +
			(ay - by) * (ay - by));

	return result;
}

int64 solve(int left, int right)
{

	if (left >= right - 1)
		return inf;
	else if (right - left == 2) {
		if (v_points[left] > v_points[left + 1])
			swap(v_points[left], v_points[left + 1]);
		return distance(points[left].first, points[left].second,
			points[left + 1].first, points[left + 1].second);
	}

	int middle = (left + right) / 2;
	int64 best = min(solve(left, middle), solve(middle, right));

	sort(v_points.begin() + left, v_points.begin() + right);

	int v_size = 0;

	for (int i = left; i < right; i++)
		if (abs(v_points[i].second - points[middle].first) <= best)
			V[v_size++] = v_points[i];

	for (int i = 0; i < v_size - 1; ++i) {
		for (int j = i + 1; j < v_size && (j - i) < 8; ++j)
			best = min(best, distance(V[i].first, V[i].second,
				V[j].first, V[j].second));
	}

	return best;

}

// int64 solve(int left, int right)
// {
// 	int64 result = 0;
// 	int size = 0, middle = 0;

// 	if (left == right)
// 		return inf;

// 	if (right - left == 1)
// 		return distance(points[right].first, points[right].second,
// 			points[left].first, points[left].second);

// 	middle = (left + right) / 2;
// 	result = min(solve(left, middle), solve(middle + 1, right));

// 	for (int i = left; i < right; i++)
// 		if (abs(v_points[i].second - points[middle].first) <= result)
// 			V[size++] = v_points[i];

// 	sort(v_points.begin() + left, v_points.begin() + right);

// 	for (int i = 0; i < size - 1; ++i) {
// 		for (int j = i + 1; j < size && (j - i) < 8; ++j)
// 			result = min(result, distance(V[i].first, V[i].second,
// 				V[j].first, V[j].second));
// 	}

// 	return result;

// }

void read_file()
{
	int64 x = 0.0, y = 0.0;

	in_file >> N;

	for (int i = 0; i < N; i++) {
		in_file >> x >> y;
		points.push_back(make_pair(x, y));
	}

	sort(points.begin(), points.end());

	for (int i = 0; i < N; i++)
		v_points.push_back(make_pair(points[i].second,
			points[i].first));

}

int main()
{

	in_file.open(in_file_name, ios::in);
	die(!in_file, "Error opening file for reading");

	out_file.open(out_file_name, ios::out);
	die(!out_file, "Error opening file for writing");

	read_file();

	out_file.precision(6);

	out_file << fixed << sqrt(solve(0, N));

	in_file.close();
	out_file.close();

	return 0;
}