Cod sursa(job #1401390)

Utilizator smaraldaSmaranda Dinu smaralda Data 25 martie 2015 20:33:37
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
using namespace std;

#define x first
#define y second
#define LL long long
const int NMAX = 405;
const double eps = 1.e-5;

pair <double, double> soldat[NMAX], adapost[NMAX];
int n, left[NMAX];
bool vis[NMAX];
double lim, dist[NMAX][NMAX];

pair <double, double> read() {
    double x, y;
    scanf("%lf%lf", &x, &y);
    return make_pair(x, y);
}

bool pairUp (int node) {
    if(vis[node])
        return 0;

    vis[node] = 1;
    for(int i = 1; i <= n; ++ i) {
        if(dist[node][i] > lim - eps)
            continue;
        if(!left[i] || pairUp(left[i])) {
            left[i] = node;
            return 1;
        }
    }

    return 0;
}

int cuplaj () {
    memset(left, 0, sizeof(left));
    int i, ans;

    ans = 0;
    for(i = 1; i <= n; ++ i) {
        memset(vis, 0, sizeof(vis));
        ans += pairUp(i);
    }
    return ans;
}

double bs (double left, double right) {
    double last;

    while(left <= right) {
        lim = (left + right) / 2;

        if(cuplaj() >= n) {
            last = lim;
            right = lim - eps;
        }
        else
            left = lim + eps;
    }
    return last;
}

double sqr (double x) {
    return x * x;
}

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

    scanf("%d\n", &n);
    for(i = 1; i <= n; ++ i)
        soldat[i] = read();
    for(i = 1; i <= n; ++ i)
        adapost[i] = read();

    for(i = 1; i <= n; ++ i)
        for(j = 1; j <= n; ++ j)
            dist[i][j] = sqrt(sqr(soldat[i].x - adapost[j].x) + sqr(soldat[i].y - adapost[j].y));

    printf("%.3lf", (double)bs(0, 3000));
    return 0;
}