Cod sursa(job #1021542)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 3 noiembrie 2013 22:45:26
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.23 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iomanip>

const static int NMAX = 100000;

using namespace std;

class Point2D
{
public:
	int x , y;
	Point2D(const int & x , const int & y);
	Point2D():x(0),y(0){};
	bool operator<(const Point2D & other) const;
	bool operator>(const Point2D & other) const;
};

Point2D::Point2D(const int & x , const int & y)
{
	this->x = x;
	this->y = y;
}

double distancePoints(const Point2D & point1 , const Point2D & point2)
{
	int dif1 = point2.x - point1.x;
	int dif2 = point2.y - point1.y;
	return sqrt(dif1 * dif1 + dif2 * dif2);
}

bool Point2D::operator< (const Point2D & other) const
{
	if (x < other.x) return true;
	else if (x > other.x) return false;
	else return (y < other.y);
}

bool Point2D::operator>(const Point2D & other) const
{
	if (x > other.x) return true;
	else if (x < other.x) return false;
	else return (y < other.y);
}

vector<Point2D> points;

int nr_points = 0;
ifstream input("cmap.in");
ofstream output("cmap.out");

double divide_and_conquer(int left , int right)
{
	if (right - left <= 3)
	{
		double min_distance = 10000.0;
		for (int i = left;i<=right;i++)
			for (int j = left;j<=right;j++)
				if (i != j && min_distance > distancePoints(points[i],points[j]))
				{
					min_distance = distancePoints(points[i],points[j]);
				}

		return min_distance;
	}
	else
	{
		int middle = (left + right) >> 1;
		double d1 = divide_and_conquer(left , middle);
		double d2 = divide_and_conquer(middle + 1 , right);
		double d = min(d1 , d2);

		vector<Point2D> v(right - left + 1);
		int p = 0;
		for (int i = left , p = 0;i<=right;i++,p++)
			v[p] = points[i];

		for (int i = 0; i < p; ++i) 
	        for (int j = i + 1; j < p && (j - i) < 8; ++j)
            	d = min(d, distancePoints(v[i], v[j]));
        return d;
	}
}

int main(int argc , char * argv[])
{
	input >> nr_points;
	for (int i = 0;i<nr_points;i++)
	{
		int  x , y;
		input >> x >> y;
		points.push_back(Point2D(x,y));
	}
	sort(points.begin(),points.end());

	output << setprecision(20) << divide_and_conquer(0 , nr_points - 1);
	input.close();
	output.close();
	return 0;
}