Cod sursa(job #1045739)

Utilizator nutipasa16Macovei Claudiu nutipasa16 Data 1 decembrie 2013 22:51:45
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
using namespace std;
 
ifstream f("cmap.in");
ofstream g("cmap.out");
 
const int MAX_N = 100005;
const long long INF = (1<<31) - 1;

class Punct
{
public:
	long long x, y;
	Punct(){}
	Punct(long long a, long long b){
		x = a;
		y = b;
	}
	bool operator > (const Punct ob) const{
		return !(x < ob.x);
	}
	bool operator < (const Punct ob) const{
		if(x < ob.x)
			return true;
		else
			if(x == ob.x){
				if(y <= ob.y)
					return true;
				else
					return false;
			}
			else
				return false;
	}
	Punct operator = (const Punct ob){
		x = ob.x;
		y = ob.y;
		return *this;
	}
	friend ostream& operator<<(const ostream&out, const Punct& ob );
};

vector < Punct > V(MAX_N), X, Y;
 
long long dist(const Punct &a, const Punct &b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

long long go(int st, int dr, vector < Punct >& X, vector < Punct >& 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;
    long long best = min(go(st, mid, X, Y), go(mid, dr, X, Y));
 
    merge(Y.begin() + st, Y.begin() + mid, Y.begin() + mid, Y.begin() + dr, V.begin());
    copy(V.begin(), V.begin() + (dr - st), Y.begin() + st);
    int v_size = 0;
    for (int i = st; i < dr; ++ i) if (abs(Y[i].y - X[mid].x) <= 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() {
    int n;
	f>>n;
	X.resize(n), Y.resize(n);
    
	for (int i = 0; i < (int) X.size(); ++ i) {
		f>>X[i].x>>X[i].y;
    }
    
    sort(X.begin(), X.end());
    for (int i = 0; i < (int) X.size(); ++ i)
	{
		Y[i].x = X[i].y;
		Y[i].y = X[i].x;
	}
 
    g << fixed << setprecision(6) << sqrt((double)go(0, (int) X.size(), X, Y)) << "\n";
    g.close();
    return 0;
}