Cod sursa(job #869941)

Utilizator BitOneSAlexandru BitOne Data 2 februarie 2013 16:48:13
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.31 kb
#include <cmath>
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define cin in
#define cout out

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

const int NMAX = 100011;

pr X[NMAX], Y[NMAX], aux[NMAX];

inline lld  _min(const lld& x, const lld& y)  {return x <= y ? x : y;}
inline void _swap(pr& x, pr& y)               {pr aux = x; x = y; y = aux;}
inline lld  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);}

lld closestPoints(int left, int right)
{
    lld minDSquare;

    if(left >= right) return -1;
    if(right - left <= 3)
    {
	minDSquare = dSquare(X[left], X[left + 1]);
        for(int i = left; i < right; ++i)
	{
	    for(int j = i + 1; j <= right; ++j)
	    {
		minDSquare = _min(minDSquare, dSquare(X[i], X[j]));
                if(Y[i].second > Y[j].second)
		{
		    _swap(Y[i], Y[j]);
		}
	    }
	}
    }
    else {
	     int i, j, k, middle;

             middle = (left + right) >> 1;
             minDSquare = _min(closestPoints(left, middle), closestPoints(middle + 1, right));

             for(i = k = left, j = middle + 1; i <= middle && j <= right; )
	     {
		 if(Y[i].second <= Y[j].second)
		 {
		     aux[k++] = Y[i++]; 
		 }
		 else {
		         aux[k++] = Y[j++];
		      }
	     }
             for(; i <= middle; ++i, ++k) aux[k] = Y[i];
             for(; j <= right;  ++j, ++k) aux[k] = Y[j];
             for(i = left; i <= right; ++i) Y[i] = aux[i];

             for(k = 0, i = left; i <= right; ++i)
	     {
		 if(1LL * abs(X[middle].first - Y[i].first)   <= minDSquare)
		 {
		     aux[k++] = Y[i];
		 }
	     }
             k -= 1;
             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(int N)
{
    sort(X, X + N);    
    return sqrt(1.0 * closestPoints(0, N - 1));
}

int main()
{
    int N, i;
    ifstream in("cmap.in");
    ofstream out("cmap.out");

    cin >> N;
    for(i = 0; i < N; ++i)
    {
	cin >> X[i].first >> X[i].second;
        Y[i] = X[i];
    }
    cout << fixed << setprecision(6) << closestPoints(N) << '\n';

    return EXIT_SUCCESS;    
}