Cod sursa(job #2304715)

Utilizator madalina.caeaMadalina Caea madalina.caea Data 18 decembrie 2018 16:03:10
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include<math.h>

using namespace std;
int n;
struct Point
{
	int x;
	int y;
};

bool sort_x(const Point& left, const Point& right)
{
	return left.x < right.x;
}

bool sort_y(const Point& left, const Point& right)
{
	return left.y < right.y;
}

long double dist(const Point& left, const Point& right)
{
	const long diffX = left.x - right.x;
	const long diffY = left.y - right.y;

	return diffX * diffX + diffY * diffY;
}

long double dist_min(const vector<Point>& points, int left, int right)
{
	if (right - left == 1)
	{
		return dist(points[left], points[right]);
	}

	if (right - left == 2)
	{
		return min(dist(points[left], points[left + 1]),
               min(dist(points[left + 1], points[right]),dist(points[left], points[right])));
	}

	const int mid = (left + right) / 2;
	const double dist1 = dist_min(points, left, mid);
	const double dist2 = dist_min(points, mid + 1, right);

	long double minDist = min(dist1, dist2);
	long double delta = sqrt(minDist);  //distanta min dintre doua puncte din regiuni diferite

	vector<Point> band;
	for (int i = left; i <= right; ++i)
	{
		if ((points[i].x - points[mid].x) <= delta)
		{
			band.push_back(points[i]);
		}
	}

	//sort(band.begin(), band.end(), sort_y);//merge sort
	inplace_merge (band.begin(),band.begin()+(n/2),band.end(),sort_y);
	for (int i = 0; i < band.size(); ++i)
	{
		for (int j = i + 1; j <= (i + 7) && j < band.size(); ++j)
		{
			minDist = min(minDist, dist(band[i], band[j]));
		}
	}

	return minDist;
}

int main()
{
	 vector<Point> points;
	 Point aux;

	 ifstream fin("cmap.in");
	 ofstream fout("cmap.out");

	 fin>>n;
	 for(int i=0; i<n; i++)
     {
       fin>>aux.x>>aux.y;
        points.push_back(aux);
     }


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

	fout<< sqrt(dist_min(points, 0, points.size() - 1)) << endl;
}