Cod sursa(job #869166)

Utilizator enedumitruene dumitru enedumitru Data 1 februarie 2013 00:44:07
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define I9 2000000000
using namespace std;
ifstream f("cmap.in"); ofstream g("cmap.out");
typedef long long i64;
const int MAX_N = 100005;
i64 INF=I9*I9;
vector < pair <i64, i64> > V(MAX_N), X, Y;
i64 dist(const pair <i64, i64>& a, const pair <i64, i64>& b) 
{return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);}

i64 go(int st, int dr, vector < pair <i64, i64> >& X, vector < pair <i64, i64> >& Y) 
{   if (st >= dr - 1) return INF;
		else if (dr - st == 2)
			{if (Y[st] > Y[st + 1]) swap(Y[st], Y[st + 1]);
			 return dist(X[st], X[st + 1]);
			}
    int mid = (st + dr) / 2;
    i64 best = min(go(st, mid, X, Y), go(mid, dr, X, Y));
    sort(Y.begin() + st, Y.begin() + dr);
    int v_size = 0;
    for (int i = st; i < dr; ++ i) if (abs(Y[i].second - X[mid].first) <= best) V[v_size ++] = Y[i];
    for (int i = 0; i < v_size - 1; ++ i) 
		{for (int j = i + 1; j < v_size && j - i < 8; ++ j)
		 best = min(best, dist(V[i], V[j]));
		}
    return best;
}
int main(void) 
{   int n;
	X.resize(n), Y.resize(n);
    for (int i = 0; i < (int) X.size(); ++ i) f >> X[i].first >> X[i].second;
    sort(X.begin(), X.end());
    for (int i = 0; i < (int) X.size(); ++ i) Y[i] = make_pair(X[i].second, X[i].first);
	g<< fixed << setprecision(6) << sqrt((double)go(0, (int) X.size(), X, Y)) << "\n";
    g.close(); return 0;
}