Cod sursa(job #988126)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 22 august 2013 00:55:17
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.41 kb
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
using namespace std;
  
const string file = "cmap";
  
const string infile = file + ".in";
const string outfile = file + ".out";

typedef long long int64;
int N;
struct Point2D
{
	int x;
	int y;
};

int predXY(const Point2D& a, const Point2D& b)
{
	if(a.x != b.x)
	{
		return a.x < b.x;
	}
	else
	{
		return a.y < b.y;
	}
}

int predYX(const Point2D& a, const Point2D& b)
{
	if(a.y != b.y)
	{
		return a.y < b.y;
	}
	else
	{
		return a.x < b.x;
	}
}

int64 dist(const Point2D& a, const Point2D& b)
{
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

vector<Point2D> pointsX;
vector<Point2D> pointsY;
vector<Point2D> centered;

const int64 INF = 1LL<<62;

int64 Closest(int st, int dr)
{
	if(st >= dr) return INF;
	else if(dr - st == 1)
	{
		sort(pointsY.begin() + st, pointsY.begin() + dr + 1, predYX);
		return dist( pointsX[st], pointsX[dr]);
	}

	int mij = (dr - st)/2 + st;

	int64 minimum = min(Closest(st, mij), Closest(mij + 1, dr));

	sort(pointsY.begin() + st, pointsY.begin() + dr + 1, predYX);

	int cSize = 0;
	for(vector<Point2D>::iterator itr = pointsY.begin() + st;
		itr != pointsY.begin() + dr + 1;
		itr++)
	{
		if(abs(itr->x - pointsX[mij].x) <= minimum)
		{
			centered[cSize++] = *itr;
		}
	}

	for(int i = 0; i < cSize; i++)
	{
		for(int j = i + 1; j < cSize && j < i + 8 ; j++)
		{
			minimum = min(minimum, dist(centered[i], centered[j]));
		}
	}
	return minimum;
}

int main()
{
	fstream fin(infile.c_str(), ios::in);
	fin >> N;
	pointsX.resize(N);
	pointsY.resize(N);

	centered.resize(N);

	for(int i = 0; i < N; i++)
	{
		int x, y;
		fin >> x >> y;
		pointsX[i].x = pointsY[i].x = x;
		pointsX[i].y = pointsY[i].y = y;
		
	}

	fin.close();

	sort(pointsX.begin(), pointsX.end(), predXY);

	fstream fout(outfile.c_str(), ios::out);
	fout << fixed << setprecision(6) << sqrt(Closest(0, N - 1)) << "\n";
	fout.close();
}