Cod sursa(job #1401254)

Utilizator smaraldaSmaranda Dinu smaralda Data 25 martie 2015 18:48:10
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 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;

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

pair <int, int> read() {
    char ln[20];
    int x, y, i;

    gets(ln);
    i = x = 0;
    while(ln[i] != ' ') {
        if(ln[i] >= '0' && ln[i] <= '9')
            x = x * 10 + ln[i] - '0';
        ++ i;
    }

    ++ i;
    y = 0;
    while(ln[i]) {
        if(ln[i] >= '0' && ln[i] <= '9')
        y = y * 10 + ln[i] - '0';
        ++ i;
    }

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

int bs (LL left, LL right) {
    LL last;

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

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

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] = (soldat[i].x - adapost[j].x) * (soldat[i].x - adapost[j].x) + (soldat[i].y - adapost[j].y) * (soldat[i].y - adapost[j].y);

    printf("%.3lf", (double)bs(0, 1e6) / 1000);
    return 0;
}