Cod sursa(job #1402698)

Utilizator smaraldaSmaranda Dinu smaralda Data 26 martie 2015 18:52:12
Problema Adapost Scor 26
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 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-6;
 
pair <double, double> soldat[NMAX], adapost[NMAX];
int n, match[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)
            continue;
        if(!match[i] || pairUp(match[i])) {
            match[i] = node;
            return 1;
        }
    }
 
    return 0;
}
 
int cuplaj () {
    memset(match, 0, sizeof(match));
    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;
    int step;

    for(step = 1; step <= 60; ++ step) {
        lim = (left + right) * 0.5;
 
        if(cuplaj() == n) {
            last = lim;
            right = lim;
        }
        else
            left = lim;
    }

    return last;
}
 
double sqr (double x) {
    return x * x;
}
 
int main() {
    freopen("adapost.in", "r", stdin);
    freopen("adapost.out", "w", stdout);
    int i, j;
 
    scanf("%d", &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("%lf 0\n", (double)bs(0, 5000));
    return 0;
}