Cod sursa(job #1015782)

Utilizator ELHoriaHoria Cretescu ELHoria Data 25 octombrie 2013 09:45:52
Problema Adapost Scor 26
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>


using namespace std;
   
const int NMAX = 402;
const double eps = 0.0001;
double inf = 1.0*int(1e9);
   
int n;
double ww[NMAX][NMAX];
double w[NMAX][NMAX], ax[NMAX], ay[NMAX];
double x[2][NMAX], y[2][NMAX];
bool vx[NMAX], vy[NMAX];
int mch[NMAX];
double maxDist, distSum;
vector< double > distances;

inline double dist(double x1,double y1,double x2,double y2) {
	return sqrt( (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
}
   
bool dfs(int x){
    vx[x] = 1;
    for(int y = 0; y < n; y++){
        int t = ax[x] + ay[y] - w[x][y];
        if(!vy[y] && t == 0){
            vy[y] = 1;
            if(mch[y] < 0 || dfs(mch[y])) {
                mch[y] = x;
                return 1;
            }
        }
    }
    return 0;
}
   
bool khun(const int &index){
	double upperBound = distances[index] + eps;
  	for(int i = 0;i < n;i++) {
		ax[i] = 0.0;
		ay[i] = 0.0;
		vx[i] = vy[i] = false;
		mch[i] = -1;
	}
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
			w[i][j] = ww[i][j] < upperBound ? -ww[i][j] : -inf;
            ax[i] = max(ax[i], w[i][j]);
        }
    }

    for(int i = 0; i < n; i++){
        while(!dfs(i)){
            double d = inf;
            for(int j = 0; j < n; j++) {
                if(!vy[j]) {
                    for(int k = 0; k < n; k++) {
                        if(vx[k]) {
							d = min(d, ax[k] + ay[j] - w[k][j]);
                        }
                    }
                }
            }
            for(int j = 0; j < n; j++) {
                if(vx[j]) ax[j] -= d, vx[j] = 0;
                if(vy[j]) ay[j] += d, vy[j] = 0;
            }
        }
    }
	double currentSum = 0.0;
	for(int i = 0;i < n;i++) {
		if(w[mch[i]][i] == -inf) {
			return false;
		}
		currentSum += ww[mch[i]][i];
	}
	maxDist = distances[index];
	distSum = currentSum;
	return true;
}

void readData() {
	scanf("%d",&n);
	for(int k = 0;k < 2;k++) {
		for(int i = 0;i < n;i++) {
			scanf("%lf %lf",&x[k][i],&y[k][i]);
		}
	}
    
}

void buildGraph() {
	distances.resize(n*n);
	for(int i = 0;i < n;i++) {
		for(int j = 0;j < n;j++) {
			ww[i][j] = dist(x[0][i],y[0][i],x[1][j],y[1][j]);
			distances[n*i + j] = ww[i][j];
			
		}
	}

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

void solve() {
	maxDist = inf;
	int left = 0, right = n*n - 1;
	while(left <= right) {
		int mid = (left + right)>>1;

		if(khun(mid)) {
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	printf("%.5lf %.5lf\n",maxDist,distSum);
}
   
int main ()
{
    freopen("adapost.in","r",stdin);
    freopen("adapost.out","w",stdout);
   
	readData();
	buildGraph();
	solve();
 
    return 0;
}