Cod sursa(job #1519001)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 6 noiembrie 2015 18:08:30
Problema Adapost Scor 22
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.33 kb
#include <fstream>
#include <vector>
#include <queue>
#include <iomanip>
#include <cmath>
#include <cstring>

#define DIM (400 + 5)
#define INF (1 << 30)

using namespace std;

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

int n;

int source, destination;

double solution;

pair<double, double> soldiers[DIM], shelters[DIM];

double capacity[2 * DIM][2 * DIM], cost[2 * DIM][2 * DIM], flux[2 * DIM][2 * DIM];

int parent[2 * DIM];

double d[2 * DIM];

double Distance(int x, int y) {

    return sqrt((soldiers[x].first - shelters[y].first)  * (soldiers[x].first - shelters[y].first) + (soldiers[x].second - shelters[y].second)  * (soldiers[x].second - shelters[y].second));

}

bool BF() {

    queue<int> Q;

    for (int i = source; i <= destination; i++) {

        parent[i] = 0;
        d[i] = INF;

    }

    parent[source] = -1;
    d[source] = 0;

    Q.push(source);

    while (Q.size()) {

        int node = Q.front();

        Q.pop();

        int add = n;

        if(node == 0 || (node > n && node < destination))
            add = 0;


        for (int i = 1; i <= n; i++) {

            int child = i + add;
            double C = cost[node][child];

            if (capacity[node][child] > flux[node][child] && d[node] + C < d[child]) {

                d[child] = d[node] + C;
                parent[child] = node;

                Q.push(child);

            }

        }

        if(!add && node != source){

            int child = destination;
            double C = cost[node][child];

            if (capacity[node][child] > flux[node][child] && d[node] + C < d[child]) {

                d[child] = d[node] + C;
                parent[child] = node;

                Q.push(child);

            }

        }
        else if (add && node != destination){

            int child = source;
            double C = cost[node][child];

            if (capacity[node][child] > flux[node][child] && d[node] + C < d[child]) {

                d[child] = d[node] + C;
                parent[child] = node;

                Q.push(child);

            }

        }

    }

    return (d[destination] != INF);

}

bool verif(double dist) {

    source = 0, destination = 2 * n + 1;

    memset(flux, 0, sizeof flux);
    memset(cost, 0, sizeof cost);
    memset(capacity, 0, sizeof capacity);

    solution = 0;

    for (int i = 1; i <= n; i++) {

        capacity[source][i] = 1;

        capacity[i + n][destination] = 1;

    }

    for (int i = 1; i <= n; i++) {

        for (int j = 1; j <= n; j++) {

            if ( Distance(i, j) - dist < 0.000001) {

                capacity[i][j + n] = 1;

                cost[i][j + n] = Distance(i, j);
                cost[j + n][i] = -Distance(i, j);

            }

        }

    }

    int maxflow = 0;

    while (BF()) {

        int var = parent[destination];

        if (capacity[var][destination] <= flux[var][destination])
            continue;


        double minim = capacity[var][destination] - flux[var][destination];

        while (parent[var] != -1){

            minim = min(minim, capacity[parent[var]][var] - flux[parent[var]][var]);

            var = parent[var];

        }

        var = parent[destination];
        flux[var][destination] += minim;
        flux[destination][var] -= minim;

        while (parent[var] != -1){

            flux[parent[var]][var] += minim;
            flux[var][parent[var]] -= minim;

            var = parent[var];

        }

        solution += d[destination] * minim;
        maxflow += minim;

    }

    return(maxflow == n);

}

void binarySearch() {

    double left = 0, right = 1500;

    while(left <= right) {

        double middle = (left + right) / 2;

        if(verif(middle))
            right = middle - 0.00001;
        else
            left = middle + 0.00001;

    }

    verif(left);

    fout << setprecision(6) << fixed;
    fout << left << " " << solution << "\n";

}

int main () {

    fin >> n;

    for (int i = 1; i <= n; i++)
         fin >> soldiers[i].first >> soldiers[i].second;

    for (int i = 1; i <= n; i++)
         fin >> shelters[i].first >> shelters[i].second;

    binarySearch();

    return 0;

}

//Miriam e tare!