Cod sursa(job #1021592)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 3 noiembrie 2013 23:24:02
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.44 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;

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 <= 2)
	{
		if (right - left == 0) return 1 << 30;
		double min_distance = distancePoints(points[left] , points[right]);
		if (right - left == 1) return min_distance;
		min_distance = min(min_distance , distancePoints(points[left] , points[left + 1]));
		min_distance = min(min_distance , distancePoints(points[left+1] , points[right]));
		return min_distance;
	}
	else
	{
		int middle = (left + right) >> 1;
		double d1 = divide_and_conquer(left , middle);
		double d2 = divide_and_conquer(middle + 1 , right);

		cout << d1 << " " <<d2 << "\n";

		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];

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

		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;
}