Cod sursa(job #2269343)

Utilizator rares9301Sarmasag Rares rares9301 Data 25 octombrie 2018 21:31:47
Problema Adapost Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.37 kb

#include <bits/stdc++.h>

 

using namespace std;

 

const int MAX_N = 400;

const double INF = 1000000;

const double eps = 1.e-6;

 

struct Punct {

  double x, y;

}s[MAX_N + 5], a[MAX_N + 5];

 

struct Date {

  int u, v;

  double d;

  bool operator < (const Date& other) const {

    return d - other.d < eps;

  }

}aux[MAX_N * MAX_N + 5];

 

double distanta(Punct a, Punct b) {

  return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));

}

 

vector<int>E[MAX_N + 5];

vector<int>G[(2 * MAX_N + 2) + 5];

int l[MAX_N + 5], r[MAX_N + 5];

bool viz[MAX_N + 5];

 

bool match(int nod) {

  if (viz[nod])

    return false;

  viz[nod] = 1;

  for (auto it:E[nod]) {

    if (l[it] == 0) {

      r[nod] = it;

      l[it] = nod;

      return true;

    }

  }

  for (auto it:E[nod]) {

    if (!viz[l[it]] && match(l[it])) {

      r[nod] = it;

      l[it] = nod;

      return true;

    }

  }

  return false;

}

 

int cuplaj(int med, int n) {

  for (int i = 1; i <= med; ++i)

    E[aux[i].u].push_back(aux[i].v);

  memset(l, 0, sizeof(l));

  memset(r, 0, sizeof(r));

  bool ok;

  do {

    ok = false;

    memset(viz, 0, sizeof(viz));

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

      if (r[i] == 0 && match(i))

        ok = true;

    }

  } while (ok);

  int ans = 0;

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

    E[i].clear();

    if (r[i])

      ans++;

  }

  return ans;

}

 

int nrv[(2 * MAX_N + 2) + 5];

bool inc[(2 * MAX_N + 2) + 5];

double dist[(2 * MAX_N + 2) + 5];

int from[(2 * MAX_N + 2) + 5];

int cr[(2 * MAX_N + 2) + 5][(2 * MAX_N + 2) + 5];

double cost[(2 * MAX_N + 2) + 5][(2 * MAX_N + 2) + 5];

 

double bellman(int s, int d, int n) {

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

    dist[i] = INF;

    nrv[i] = 0;

    inc[i] = 0;

  }

  inc[s] = 1;

  from[s] = s;

  nrv[s] = 1;

  dist[s] = 0;

  queue<int>q;

  q.push(s);

  while (!q.empty() && nrv[q.front()] < n) {

    int node = q.front();

    q.pop();

    inc[node] = 0;

    for (auto it:G[node]) {

      if (cr[node][it] > 0 && dist[node] + cost[node][it] - dist[it] < eps) {

        from[it] = node;

        dist[it] = dist[node] + cost[node][it];

        if (inc[it] == 0) {

          inc[it] = 1;

          q.push(it);

          nrv[it]++;

        }

      }

    }

  }

  return dist[d];

}

 

double cmcm(int s, int d, int n) {

  double ans = 0, dm;

  dm = bellman(s, d, n);

  while (dm != INF) {

    int aux = INF;

    int node = d;

    while (node != s) {

      aux = min(aux, cr[from[node]][node]);

      node = from[node];

    }

    node = d;

    while (node != s) {

      cr[from[node]][node] -= aux;

      cr[node][from[node]] += aux;

      node = from[node];

    }

    ans += dm * aux;

    dm = bellman(s, d, n);

  }

 

  return ans;

}

 

int main() {

  freopen("adapost.in", "r", stdin);

  freopen("adapost.out", "w", stdout);

 

  int n;

  scanf("%d", &n);

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

    scanf("%lf%lf", &s[i].x, &s[i].y);

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

    scanf("%lf%lf", &a[i].x, &a[i].y);

  int k = 0;

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

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

      aux[++k] = {i, j, distanta(s[i], a[j])};

  sort(aux + 1, aux + k + 1);

  int st = 1, dr = k;

  int last = 0;

  while (st <= dr) {

    int med = (st + dr) >> 1;

    if (cuplaj(med, n) == n) {

      last = med;

      dr = med - 1;

    } else {

      st = med + 1;

    }

  }

 

  printf("%.4f ", aux[last].d);

 

  //return 0;

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

    G[aux[i].u + 1].push_back(aux[i].v + n + 1);

    G[aux[i].v + n + 1].push_back(aux[i].u + 1);

    cr[aux[i].u + 1][aux[i].v + n + 1] = 1;

    cost[aux[i].u + 1][aux[i].v + n + 1] = aux[i].d;

    cost[aux[i].v + n + 1][aux[i].u + 1] = -aux[i].d;

  }

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

    G[1].push_back(i);

    G[i].push_back(1);

    cr[1][i] = 1;

  }

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

    G[i].push_back(2 * n + 2);

    G[2 * n + 2].push_back(i);

    cr[i][2 * n + 2] = 1;

  }

  printf("%.4f\n", cmcm(1, 2 * n + 2, 2 * n + 2));

 

  return 0;

}