Pagini recente » Cod sursa (job #448427) | Cod sursa (job #2672293) | Cod sursa (job #2851583) | Cod sursa (job #2947449) | Cod sursa (job #33835)
Cod sursa(job #33835)
#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;
}