Cod sursa(job #33428)

Utilizator alextheroTandrau Alexandru alexthero Data 19 martie 2007 13:11:30
Problema Adapost Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.19 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <vector>

#define sqr(i) ((i) * (i))
#define nmax 512
#define inf 1e10 
#define pb push_back

using namespace std;

vector <int> e[2 * nmax];
int n,p;
int cuplat[2 * nmax],prev[2 * nmax];
double sx[nmax],sy[nmax],fx[nmax],fy[nmax],dist[nmax * nmax];
double maxdist,di[2 * nmax];
char v[2 * nmax];
char cap[2 * nmax][2 * nmax],fl[2 * nmax][2 * nmax];
double cost[2 * nmax][2 * nmax];

inline double d(int i,int j) {
	if(cost[i][n + j] == 0) {
		cost[i][n + j] = sqrt(sqr(sx[i] - fx[j]) + sqr(sy[i] - fy[j]));	
		cost[n + j][i] = - cost[i][n + j];
	}
	return cost[i][n + j];
}

int cupleaza(int x) {
	if(v[x]) return 0;
	v[x] = 1;
	if(x <= n) for(int j = 1; j <= n; j++) 
		if(d(x,j) <= maxdist) 
			if(!v[n + j] && (!cuplat[n + j] || cupleaza(cuplat[n + j]))) {
				cuplat[x] = n + j;
				cuplat[n + j] = x;
				return 1;
			}
	else for(int j = 1; j <= n; j++) 
		if(d(j,x - n) <= maxdist)
			if(!v[j] && (!cuplat[j] || cupleaza(cuplat[j]))) {
				cuplat[x] = j;
				cuplat[j] = x;
				return 1;
			}
	return 0;
}

int bun(int x) {
	memset(v,0,sizeof(v));
	memset(cuplat,0,sizeof(cuplat));
	maxdist = dist[x];
	for(int i = 1; i <= n; i++) 
		if(!cupleaza(i)) {
			memset(v,0,sizeof(v));
			cupleaza(i);
		}
	int r = 0;
	for(int i = 1; i <= n; i++) if(cuplat[i]) r++;
	if(r == n) return 1;
	else return 0;
}

int cauta(int f,int l) {
	int r = 0;
	while(f <= l) {
		int m = (f + l) / 2;
		if(bun(m)) {
			r = m;
			l = m - 1;
		}
		else f = m + 1;
	}
	return r;
}

void capacities(int x) {
	for(int i = 1; i <= n; i++) cap[0][i] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++) if(cost[i][j + n] <= dist[x]) cap[i][j + n] = 1;
	for(int i = 1; i <= n; i++) cap[i + n][2 * n + 1] = 1;
}

int drum() {
	for(int i = 1; i <= n; i++) {
		e[i + n].pb(2 * n + 1);
		e[0].pb(i);
		for(int j = n + 1; j <= 2 * n; j++) 
		if(cost[i][j] <= maxdist) 
		{
			e[i].pb(j);
			e[j].pb(i);
		}
	}

	for(int i = 0; i <= 2 * n + 1; i++) {
		di[i] = inf;
		prev[i] = -1;
	}

	di[0] = 0;

	for(int pas = 0; pas <= 2 * n + 1; pas++) {
		int gata = 1;
		for(int i = 0; i <= 2 * n + 1; i++)
			if(di[i] != inf)
				for(int j = 0; j < (int)e[i].size(); j++) 
					if(cap[i][e[i][j]] > fl[i][e[i][j]]) {
						double nd = di[i] + cost[i][e[i][j]];
						if(di[e[i][j]] > nd) {
							di[e[i][j]] = nd;
							prev[e[i][j]] = i;
							gata = 0;
						}
					}
		if(gata) break;
	}

	if(di[2 * n + 1] == inf) return 0;
	else {
		int x = 2 * n + 1;
		while(prev[x] != -1) {
			fl[prev[x]][x] = 1;
			fl[x][prev[x]] = - fl[prev[x]][x];
			x = prev[x];
		}
		return 1;
	}
}

void max_flow() {
	while(drum()) ; 
	double tot = 0;
	for(int i = 1; i <= n; i++) 
		for(int j = n + 1; j <= 2 * n; j++)
			if(fl[i][j] == 1) tot += cost[i][j];
	printf("%lf\n",tot);
}

int main() {
	freopen("adapost.in","r",stdin);
	freopen("adapost.out","w",stdout);
	
	scanf("%d",&n);
	for(int i = 1; i <= n; i++) scanf("%lf%lf",&sx[i],&sy[i]);
	for(int i = 1; i <= n; i++) scanf("%lf%lf",&fx[i],&fy[i]);

	p = 0;
	for(int i = 1; i <= n; i++) 
		for(int j = 1; j <= n; j++) dist[++p] = d(i,j);

	sort(dist + 1, dist + p + 1);

	int x = cauta(1,p);

	printf("%lf ",dist[x]);

	capacities(x);
	max_flow();

	return 0;
}