Cod sursa(job #1015395)

Utilizator freak93Adrian Budau freak93 Data 24 octombrie 2013 16:16:41
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.9 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<double, double> Soldier, Shelter;

class SimpleGraph {
  public:
    SimpleGraph(int size):
            size_(size),
            edges_(size) {
    }

    void addEdge(int from, int to) {
        edges_[from].push_back(to);
    }

    bool didInvertChain(int from, int to) {
        queue<int> Q;
        Q.push(from);

        vector<int> parent(size_, -1);
        parent[from] = from;
        while (!Q.empty()) {
            int node = Q.front();
            Q.pop();
            if (node == to)
                break;

            for (auto &next : edges_[node])
                if (parent[next] == -1) {
                    parent[next] = node;
                    Q.push(next);
                }
        }

        if (parent[to] == -1)
            return false;
        for (int node = to; node != from; node = parent[node]) {
            vector<int> &where = edges_[parent[node]];
            where.erase(find(where.begin(), where.end(), node));
            edges_[node].push_back(parent[node]);
        }
        return true;
    }

  private:
    int size_;
    vector< vector<int> > edges_;
};

int main() {
    ifstream cin("adapost.in");
    ofstream cout("adapost.out");

    int N; cin >> N;

    vector<Soldier> A(N);
    vector<Shelter> B(N);

    for (int i = 0; i < N; ++i)
        cin >> A[i].first >> A[i].second;
    for (int i = 0; i < N; ++i)
        cin >> B[i].first >> B[i].second;

    vector< vector<double> > distance(N, vector<double>(N, 0));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            distance[i][j] = sqrt((A[i].first - B[j].first) * (A[i].first - B[j].first) + 
                                  (A[i].second - B[j].second) * (A[i].second - B[j].second));

    vector< pair<int, int> > pairs(N * N);
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            pairs[i * N + j] = {i, j};
    sort(pairs.begin(), pairs.end(), [&](pair<int, int> A, pair<int, int> B) {
        return distance[A.first][A.second] < distance[B.first][B.second];
    });

    SimpleGraph G(2 * N + 2);
    for (int i = 0; i < N; ++i) {
        G.addEdge(2 * N, i); // source to soldier
        G.addEdge(i + N, 2 * N + 1); // shelter to sink
    }

    int matches = 0;

    double maxDistance = 0;
    for (auto &pair: pairs) {
        G.addEdge(pair.first, pair.second + N);
        while (G.didInvertChain(2 * N, 2 * N + 1)) // we invert a chain between the source and sink
                                                   // at most one new chain can appear when we add an edge
            ++matches;
        if (matches == N) {
            maxDistance = distance[pair.first][pair.second];
            break;
        }
    }

    cout.setf(ios::fixed, ios::floatfield);
    cout.precision(5);
    cout << maxDistance << " ";
    cout << 1 << "\n";
}