Cod sursa(job #2798577)

Utilizator LicaMihaiIonutLica Mihai- Ionut LicaMihaiIonut Data 11 noiembrie 2021 16:21:09
Problema Adapost Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.03 kb
/*
 *      Complexity: O(N^3 * log N + N^4)
 */

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

const int MAX_N = 401;
const double INF = 1.e10;

#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 cap[2 * MAX_N + 2][2 * MAX_N + 2];
vector <short int> G[2 * MAX_N + 2];
bool visited[2 * MAX_N + 2]; short int prec[2 * MAX_N + 2];
double cost[2 * MAX_N + 2][2 * MAX_N + 2], c[2 * MAX_N + 2];
bool in_queue[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 <short int> :: iterator it = G[v].begin(); it != G[v].end(); ++it)
            if(cap[v][*it] && !visited[*it]) {
                visited[*it] = true, prec[*it] = v, Q.push(*it);
                if(*it == 2 * N + 1)
                    return;
            }
    }
}

int flux1(double MAX) {
    int T = 2 * N + 1;

    for(int i = 0; i <= T; ++i)
        G[i].clear();
    for(int i = 1; i <= N; ++i) {
        G[0].push_back(i); cap[0][i] = 1;
        G[i].push_back(0); cap[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); cap[i][j] = 1;
                G[j].push_back(i); cap[j][i] = 0;
            }
    for(int i = N + 1; i <= 2 * N; ++i) {
        G[i].push_back(T); cap[i][T] = 1;
        G[T].push_back(i); cap[T][i] = 0;
    }

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

    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);
}

void Bellman_Ford() {
    for(int i = 1; i < 2 * N + 2; ++i)
        visited[i] = false, c[i] = INF, in_queue[i] = false;
    visited[0] = true;
    c[0] = 0;
    prec[0] = -1;
    in_queue[0] = true;

    queue <int> Q;
    Q.push(0);
    while(!Q.empty()) {
        int v = Q.front();
        Q.pop();
        in_queue[v] = false;
        visited[v] = true;
        for(vector <short int> :: iterator it = G[v].begin(); it != G[v].end(); ++it)
            if(cap[v][*it] && c[v] + cost[v][*it] < c[*it]) {
                c[*it] = c[v] + cost[v][*it];
                prec[*it] = v;
                if(!in_queue[*it]) {
                    in_queue[*it] = true;
                    Q.push(*it);
                }
            }
    }
}

double flux2(double MAX) {
    int T = 2 * N + 1;

    for(int i = 0; i <= T; ++i)
        G[i].clear();
    for(int i = 1; i <= N; ++i) {
        G[0].push_back(i); cap[0][i] = 1; cost[0][i] = 0;
        G[i].push_back(0); cap[i][0] = 0; cost[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); cap[i][j] = 1; cost[i][j] = D[i][j - N];
                G[j].push_back(i); cap[j][i] = 0; cost[j][i] = -D[i][j - N];
            }
    for(int i = N + 1; i <= 2 * N; ++i) {
        G[i].push_back(T); cap[i][T] = 1; cost[i][T] = 0;
        G[T].push_back(i); cap[T][i] = 0; cost[T][i] = 0;
    }

    do {
        Bellman_Ford();
        if(visited[T]) {
            int u = prec[T], v = T;
            while(u != -1) {
                cap[u][v]--;
                cap[v][u]++;
                v = u;
                u = prec[u];
            }
        }
    } while(visited[T]);

    double cost_minim = 0;
    for(int i = 1; i <= N; ++i)
        for(int j = N + 1; j <= 2 * N; ++j)
            if(D[i][j - N] <= MAX && !cap[i][j])
                cost_minim += cost[i][j];
    return cost_minim;
}


int main() {
    read();
    init();
    double MAX = dist[binary_search(0, dist.size() - 1)];
    out << fixed << setprecision(5);
    out << MAX << " " << flux2(MAX);
    return 0;
}