Cod sursa(job #2085775)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 10 decembrie 2017 18:11:02
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4 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;
}