Cod sursa(job #869826)

Utilizator BitOneSAlexandru BitOne Data 2 februarie 2013 13:30:33
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.51 kb
#include <cmath>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <algorithm>

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

const int NMAX = 100011;

inline llu  minimum(const llu& x, const llu& y) {return x <= y ? x : y;}
inline bool cmpX(const pr& x, const pr& y)      {return x.first < y.first || (x.first == y.first && x.second < y.second);}
inline bool cmpY(const pr& x, const pr& y)      {return x.second < y.second || (x.second == y.second && x.first < y.first);}
inline llu  dSquare(pr x, pr y)                 {return 1LL * (x.first - y.first) * (x.first - y.first) + 1LL *(x.second - y.second) * (x.second - y.second);}


llu closestPair(vector<pr>& vx, vector<pr>& vy, vector<pr>& aux, int left, int right)
{
    llu min;
    if(left >= right) return 0;
    if(right - left <= 5)
    {
	min = dSquare(vx[left], vx[left + 1]);
        for(int i = left; i < right; ++i)
	{
	    for(int j = i + 1; j <= right; ++j)
	    {
		if(dSquare(vx[i], vx[j]) < min)
		{
		    min = dSquare(vx[i], vx[j]);
    		}
	    } 
	}
    }
    else {
            
	    int i, j, k, middle;
            
            middle = (left + right) >> 1;
            min = closestPair(vx, vy, aux, left, middle);
            min = minimum(min, closestPair(vx, vy, aux, middle + 1, right));

            for(k = 0, i = left; i <= right; ++i)
	    {
		if(min >= abs(vx[middle].first - vy[i].second))
		{
		    aux[k++] = vy[i];
		}
	    }       
            for(i = 0; i < k; ++i)
            {
	       for(j = 1; j + i < k && j <= 8; ++j)
	       {
	           if(dSquare(aux[i], aux[j+i]) < min)
	           {
		      min = dSquare(aux[i], aux[j+i]);
		   }
	       }
	    }
         }

    return min;
}

inline double closestPair(vector<pr>& v)
{
    vector<pr> vx(v), vy(v), aux;
    vector<pr>::iterator iendX, iendY;

    sort(vx.begin(), vx.end(), cmpX);
    sort(vy.begin(), vy.end(), cmpY);

    //iendX = unique(vx.begin(), vx.end());
    //iendY = unique(vy.begin(), vy.end());
     
    //vx.resize(distance(vx.begin(), iendX));
    //vy.resize(distance(vy.begin(), iendY));    
    aux.resize(vx.size());

    return sqrt(1.0*closestPair(vx, vy, aux, 0, vx.size() - 1));
}

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

    freopen("cmap.in", "rt", stdin);
    freopen("cmap.out", "wt", stdout);
    for(cin >> N; N; --N)
    {
	cin >> x.first >> x.second;
	v.push_back(x);
    }
    cout << fixed << setprecision(6) << closestPair(v) << '\n';
    return EXIT_SUCCESS;
}