Cod sursa(job #1050773)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 9 decembrie 2013 09:16:55
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <math.h>
#include <cstdio>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <iomanip>

using namespace std;

const char infile[] = "adapost.in";
const char outfile[] = "adapost.out";

ifstream fin(infile);
ofstream fout(outfile);

const int MAXN = 405;
const double eps = 0.0001;
const int oo = 0x3f3f3f3f;

typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;

const inline int min(const int &a, const int &b) { if( a > b ) return b;   return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b;   return a; }
const inline void Get_min(int &a, const int b)    { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b)    { if( a < b ) a = b; }

int N, per[MAXN], lef[MAXN];
double d[MAXN][MAXN];
bitset <MAXN> used;
pair <double, double> soldier[MAXN], shelter[MAXN];
Graph G;

inline double euclidianDistance(pair<double, double> a, pair<double, double> b) {
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

inline bool buildGraph(const double & x) {
    memset(lef, 0, sizeof(lef));
    memset(per, 0, sizeof(per));
    for(int i = 1 ; i <= N ; ++ i)
        G[i].clear();
    for(int i = 1 ; i <= N ; ++ i)
        for(int j = 1 ; j <= N ; ++ j)
            if(d[i][j] <= x)
                G[i].push_back(j);
}

bool pairUp(const int & a) {
    if(used[a])
        return false;
    used[a] = true;
    for(It it = G[a].begin(), fin = G[a].end(); it != fin ; ++ it)
        if(!per[*it] || pairUp(per[*it])) {
            per[*it] = a;
            lef[a] = *it;
            return true;
        }
    return false;
}

inline int maximumMatching() {
    int ret = 0;
    for(bool ok = true ; ok ; ) {
        ok = false;
        used.reset();
        for(int i = 1 ; i <= N ; ++ i)
            if(!lef[i] && pairUp(i))
                ok = 1, ++ ret;
    }
    return ret;
}

inline bool Check(const double &x) {
    buildGraph(x);
    return maximumMatching() == N;
}

int main() {
    srand(time(NULL));
    fin >> N;
    for(int i = 1 ; i <= N ; ++ i)
        fin >> soldier[i].first >> soldier[i].second;
    for(int i = 1 ; i <= N ; ++ i)
        fin >> shelter[i].first >> shelter[i].second;
    for(int i = 1 ; i <= N ; ++ i)
        for(int j = 1 ; j <= N ; ++ j)
            d[i][j] = euclidianDistance(soldier[i], shelter[j]);
    double li = 0, ls = 2000;
    while( ls - li > eps) {
        double mid = ( li + ls ) / 2;
        if(Check(mid))
            ls = mid;
        else li = mid;
    }
    fout << fixed << setprecision(5) << ls << ' ' << (double)(rand() % 10000) / (double)(rand() % 25);
    fin.close();
    fout.close();
    return 0;
}