Pagini recente » Cod sursa (job #126019) | Cod sursa (job #3212141) | Borderou de evaluare (job #1567125) | kl | Cod sursa (job #33368)
Cod sursa(job #33368)
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#define sqr(i) ((i) * (i))
#define nmax 512
using namespace std;
int n,p;
int cuplat[nmax];
double sx[nmax],sy[nmax],fx[nmax],fy[nmax],dist[nmax * nmax];
double maxdist;
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;
}
void max_flow() {
}
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;
}