Cod sursa(job #33835)

Utilizator alextheroTandrau Alexandru alexthero Data 19 martie 2007 20:53:10
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <vector>

#define pb push_back
#define nmax 512

using namespace std;

double sx[2 * nmax],sy[2 * nmax],dist[nmax * nmax];
double cost[2 * nmax][2 * nmax],maxdist;
char v[2 * nmax];
unsigned short int fl[2 * nmax][2 * nmax],cap[2 * nmax][2 * nmax];
int cuplat[2 * nmax];
int i,j,n,p;
vector <int> e[2 * nmax];

inline double sqr(double x) {
	return x * x;
}

double d(int i,int j) {
	return sqrt(sqr(sx[i] - sx[j]) + sqr(sy[i] - sy[j]));
}

int cupleaza(int x) {
	if(v[x]) return 0;
	v[x] = 1;
	int sx;
	if(x <= n) sx = n + 1;
	else sx = 1;
	for(int i = sx; i < sx + n; i++) {
		if(fabs(cost[x][i]) <= maxdist && (!cuplat[i] || cupleaza(cuplat[i]))) {
			cuplat[x] = i;
			cuplat[i] = x;
			return 1;
		}
	}
	return 0;
}

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

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

void capacities() {
	for(int i = 1; i <= n; i++) {
		cap[0][i] = 1;
		e[0].pb(i);
		cap[i + n][2 * n + 1] = 1;
		e[i + n].pb(2 * n + 1);
		for(int j = n + 1; j <= 2 * n; j++) {
			e[i].pb(j);
			cap[i][j] = 1;
			e[j].pb(i);
			cap[j][i] = 1;
		}
	}
}

int drum() {
	return 0;
}

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

int main() {
	freopen("adapost.in","r",stdin);
	freopen("adapost.out","w",stdout);
	
	scanf("%d",&n);
	for(int i = 1; i <= 2 * n; i++) scanf("%lf%lf",&sx[i],&sy[i]);
	for(int i = 1; i <= n; i++) 
		for(int j = n + 1; j <= 2 * n; j++) {
			cost[i][j] = d(i,j);
			cost[j][i] = - cost[i][j];
			dist[++p] = cost[i][j];
		}

	sort(dist + 1,dist + p + 1);
	int x = cauta(1,p);

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

	flux();

	return 0;
}