Cod sursa(job #869882)

Utilizator BitOneSAlexandru BitOne Data 2 februarie 2013 15:30:49
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.32 kb
#include <cmath>
#include <vector>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define cin in
#define cout out

using namespace std;
typedef long long int llu;
typedef pair<int, int> pr;

const int NMAX = 100011;

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

inline llu   min(const llu& x, const llu& y)   {return x <= y ? x : y;}
inline void  swap(pr& x, pr& y)                {pr aux = x; x = y; y = aux;}
inline bool  compY(const pr& x, const pr& y)   {return x.second < y.second || (x.second == y.second && x.first < y.first);}
inline llu   dSquare(const pr& x, const pr& y) {return 1LL * (x.first - y.first) * (x.first - y.first) + 1LL * (x.second - y.second) * (x.second - y.second);}

llu closestPoints(vector<pr>& vx, vector<pr>& vy, vector<pr>& aux, int left, int right)
{
    llu minDSquare;
    if(left >= right) return -1;
    if(right - left <= 10)
    {
        minDSquare = dSquare(vx[left], vx[left + 1]);
	for(int i = left; i < right; ++i)
	{
	    for(int j = i + 1; j <= right; ++j)
	    {
	        minDSquare = min(minDSquare, dSquare(vx[i], vx[j]));
	        if(vy[i].second > vy[j].second)
		{
		    swap(vy[i], vy[j]);
		}
	    }
	}
    }
    else {
	    int  i, j, k, middle;
            
            middle = (left + right) >> 1;
            minDSquare = min(closestPoints(vx, vy, aux, left, middle), closestPoints(vx, vy, aux, middle + 1, right));
            
            merge(vy.begin() + left, vy.begin() + middle + 1, vy.begin() + middle + 1, vy.begin() + right + 1, aux.begin(), compY);
            copy(aux.begin(), aux.begin() + right + 1, vy.begin() + left);
            for(i = left, k = 0; i <= right; ++i)
	    {
		if(abs(vx[middle].first - vy[i].second) <= minDSquare)
		{
		    aux[k++] = vy[i];
		}
	    }
            for(i = 0; i < k; ++i)
	    {
		for(j = i + 1; j < k && j - i < 8; ++j)
		{
		    minDSquare = min(minDSquare, dSquare(aux[i], aux[j]));
		}
	    }
         }
    return minDSquare;
}

inline double closestPoints(vector<pr>& v)
{
    vector<pr> vy(v), aux(v.size());

    sort(v.begin(), v.end());
    return sqrt(1.0 * closestPoints(v, vy, aux, 0, v.size() - 1));
}

int main()
{
    int N, x, y;
    vector<pr> v;

    for(cin >> N; N; --N)
    {
	cin >> x >> y;
        v.push_back(pr(x, y));
    }
    cout << fixed << setprecision(6) << closestPoints(v) << '\n';

    return EXIT_SUCCESS;
}