Cod sursa(job #1022022)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 4 noiembrie 2013 17:24:31
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.37 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(const Point2D & other);
	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;
}

Point2D::Point2D(const Point2D & other)
{
	x = other.x;
	y = other.y;
}

double distancePoints(const Point2D & point1 , const Point2D & point2)
{
	return sqrt(1LL *(point2.x - point1.x) * (point2.x - point1.x) + 1LL * (point2.y - point1.y) * (point2.y - point1.y));
}

bool Point2D::operator< (const Point2D & other) const
{
	return x < other.x;
}

bool Point2D::operator>(const Point2D & other) const
{
	return x > other.x;
}

vector<Point2D> points , aux_points;

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

bool cmp(const Point2D & p1 , const Point2D & p2)
{
	return p1.y < p2.y;
}

double divide_and_conquer(int left , int right)
{
	if (right <= left)
	{
		return (1 << 30);
	}
	if (right - left == 1)
	{
		return distancePoints(points[left],points[right]);
	}
	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);

		aux_points.clear();

		for (int i = left; i<=middle && points[middle].x - points[i].x <= d; i++)
			aux_points.push_back(points[i]);

		for (int i = middle + 1; i<=right && points[i].x - points[middle].x <= d; i++)
			aux_points.push_back(points[i]);

		sort(aux_points.begin() , aux_points.end() , cmp);

		int size = aux_points.size();
		for (int i = 0; i < size; ++i) 
	        for (int j = i + 1; j < size && (j - i) < 8; ++j)
            	d = min(d, distancePoints(aux_points[i], aux_points[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;
}