Pagini recente » Cod sursa (job #1950802) | Cod sursa (job #2766781) | Cod sursa (job #1450987) | Cod sursa (job #131342) | Cod sursa (job #33408)
Cod sursa(job #33408)
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#define sqr(i) ((i) * (i))
#define nmax 512
#define inf 1e10
using namespace std;
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(d(i,j) <= 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 = 0; i <= 2 * n + 1; i++) {
di[i] = inf;
prev[i] = -1;
}
di[0] = 0;
for(int pas = 0; pas <= n; pas++)
for(int i = 0; i <= 2 * n + 1; i++)
if(di[i] != inf) {
if(i == 0) {
for(int j = 1; j <= n; j++)
if(cap[i][j] > fl[i][j]) {
double nd = di[i] + cost[i][j];
if(nd < di[j]) {
di[j] = nd;
prev[j] = i;
}
}
}
else if(i <= n) {
int j = 0;
if(cap[i][j] > fl[i][j]) {
double nd = di[i] + cost[i][j];
if(nd < di[j]) {
di[j] = nd;
prev[j] = i;
}
}
for(int j = n + 1; j <= 2 * n; j++)
if(cap[i][j] > fl[i][j]) {
double nd = di[i] + cost[i][j];
if(nd < di[j]) {
di[j] = nd;
prev[j] = i;
}
}
}
else {
int j = 2 * n + 1;
if(cap[i][j] > fl[i][j]) {
double nd = di[i] + cost[i][j];
if(nd < di[j]) {
di[j] = nd;
prev[j] = i;
}
}
for(int j = 1; j <= n; j++)
if(cap[i][j] > fl[i][j]) {
double nd = di[i] + cost[i][j];
if(nd < di[j]) {
di[j] = nd;
prev[j] = i;
}
}
}
}
if(di[2 * n + 1] == inf) return 0;
else {
int x = 2 * n + 1;
int min = 100;
while(prev[x] != -1) {
if(min > cap[prev[x]][x] - fl[prev[x]][x])
min = cap[prev[x]][x] - fl[prev[x]][x];
x = prev[x];
}
x = 2 * n + 1;
while(prev[x] != -1) {
fl[prev[x]][x] += min;
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;
}