Cod sursa(job #612638)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 9 septembrie 2011 12:07:39
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int N = 405;

const double eps = 0.000001;

int n, st[N], dr[N];

double xs[N], ys[N], xa[N], ya[N];

vector <double> v;

vector <int> L[N];

bool viz[N];

void read() {
  scanf("%d", &n);

  for (int i = 1; i <= n; ++ i)
    scanf("%lf%lf", &xs[i], &ys[i]);

  for (int i = 1; i <= n; ++ i)
    scanf("%lf%lf", &xa[i], &ya[i]);
}

// distanta dintre doua puncte
double dist(double x1, double y1, double x2, double y2) {
  return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

// formez vectorul cu valorile ce pot fi luate de costurile muchiilor
void init() {
  v.push_back(0);

  for (int i = 1; i <= n; ++ i)
    for (int j = 1; j <= n; ++ j)
      v.push_back(dist(xs[i], ys[i], xa[j], ya[j]));

  sort(v.begin(), v.end());
}

void reset_graf() {
  for (int i = 1; i <= n; ++ i)
    L[i].clear();

  for (int i = 1; i <= n; ++ i)
    st[i] = dr[i] = 0;
}

// adaug in graf doar muchiile cu costuri < val
void make_graf(double val) {
  reset_graf();

  for (int i = 1; i <= n; ++ i)
    for (int j = 1; j <= n; ++ j)
      if (dist(xs[i], ys[i], xa[j], ya[j]) <= val + eps)
        L[i].push_back(j);
}

void reset(bool a[N]) {
  for (int i = 1; i <= n; ++ i)
    a[i] = 0;
}

bool pair_up(int nod) {
  if (viz[nod])
    return 0;

  viz[nod] = 1;

  for (int i = 0; i < (int)L[nod].size(); ++ i)
    if (!dr[L[nod][i]]) {
      st[nod] = L[nod][i];
      dr[L[nod][i]] = nod;
      return 1;
    }

  for (int i = 0; i < (int)L[nod].size(); ++ i)
    if (pair_up(dr[L[nod][i]])) {
      st[nod] = L[nod][i];
      dr[L[nod][i]] = nod;
      return 1;
    }

  return 0;
}

int cuplaj(double val) {
  bool ok = 1;
  int nrp = 0;

  make_graf(val);

  while (ok) {
    ok = 0;
    reset(viz);

    for (int i = 1; i <= n; ++ i)
      if (!st[i] && pair_up(i)) {
        ++ nrp;
        ok = 1;
      }
  }

  return nrp;
}

int cautb() {
  int i = 0, pas = 1;

  while ((pas << 1) < v.size())
    pas <<= 1;

  for (i = 0; pas; pas >>= 1)
    if (i + pas < v.size() && cuplaj(v[i + pas]) < n)
      i += pas;

  return i + 1;
}

int main() {
  freopen("adapost.in", "r", stdin);
  freopen("adapost.out", "w", stdout);

  read();

  init();

  double rez = v[cautb()];

  printf("%.6lf ", rez);

  printf("0\n");

  return 0;
}