Cod sursa(job #187104)

Utilizator JohnnyBravoJohnny Bravo JohnnyBravo Data 30 aprilie 2008 18:32:51
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.93 kb
/*
 *      Complexity: O(N^3 * log N)
 */

// TODO verifica corectitudinea complexitatii

#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

const int MAX_N = 401;

#define point pair <double, double>
#define x first
#define y second

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

int N;
point S[MAX_N], A[MAX_N];
double D[MAX_N][MAX_N];
vector <double> dist;

char cap1[2 * MAX_N + 2][2 * MAX_N + 2];
vector <int> G[2 * MAX_N + 2];
bool visited[2 * MAX_N + 2]; int prec[2 * MAX_N + 2];

inline double Distance(const point &A, const point &B) {
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

void read() {
    in >> N;
    for(int i = 1; i <= N; ++i)
        in >> S[i].x >> S[i].y;
    for(int i = 1; i <= N; ++i)
        in >> A[i].x >> A[i].y;
}

void init() {
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            dist.push_back(D[i][j] = Distance(S[i], A[j]));
    sort(dist.begin(), dist.end());
}

void BF() {
    for(int i = 1; i < 2 * N + 2; ++i)
        visited[i] = false;
    visited[0] = true;
    prec[0] = -1;
    queue <int> Q;
    Q.push(0);
    while(!Q.empty()) {
        int v = Q.front();
        Q.pop();
        for(vector <int> :: iterator it = G[v].begin(); it != G[v].end(); ++it)
            if(cap1[v][*it] && !visited[*it]) {
                visited[*it] = true, prec[*it] = v, Q.push(*it);
                if(*it == 2 * N + 1)
                    return;
            }
    }
}

int flux1(double MAX) {
    for(int i = 0; i < 2 * N + 2; ++i)
        G[i].clear();
    for(int i = 1; i <= N; ++i) {
        G[0].push_back(i); cap1[0][i] = 1;
        G[i].push_back(0); cap1[i][0] = 0;
    }
    for(int i = 1; i <= N; ++i)
        for(int j = N + 1; j <= 2 * N; ++j)
            if(D[i][j - N] <= MAX) {
                G[i].push_back(j); cap1[i][j] = 1;
                G[j].push_back(i); cap1[j][i] = 0;
            }
    for(int i = N + 1; i <= 2 * N; ++i) {
        G[i].push_back(2 * N + 1); cap1[i][2 * N + 1] = 1;
        G[2 * N + 1].push_back(i); cap1[2 * N + 1][i] = 0;
    }

    int flux_maxim = 0;
    do {
        BF();
        if(visited[2 * N + 1]) {
            ++flux_maxim;
            int u = prec[2 * N + 1], v = 2 * N + 1;
            while(u != -1) {
                cap1[u][v]--;
                cap1[v][u]++;
                v = u;
                u = prec[u];
            }
        }
    } while(visited[2 * N + 1]);

    return flux_maxim;
}

int binary_search(const int &lo, const int &hi) {
    if(lo == hi)
        return lo;
    if(flux1(dist[(lo + hi) / 2]) == N)
        return binary_search(lo, (lo + hi) / 2);
    else
        return binary_search((lo + hi) / 2 + 1, hi);
}


int main() {
    read();
    init();
    out << dist[binary_search(0, dist.size() - 1)] << " ";
    return 0;
}