Pagini recente » Cod sursa (job #1409) | Cod sursa (job #947712) | Cod sursa (job #2062046) | Cod sursa (job #2568945) | Cod sursa (job #1402698)
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
using namespace std;
#define x first
#define y second
#define LL long long
const int NMAX = 405;
const double eps = 1.e-6;
pair <double, double> soldat[NMAX], adapost[NMAX];
int n, match[NMAX];
bool vis[NMAX];
double lim, dist[NMAX][NMAX];
pair <double, double> read() {
double x, y;
scanf("%lf%lf", &x, &y);
return make_pair(x, y);
}
bool pairUp (int node) {
if(vis[node])
return 0;
vis[node] = 1;
for(int i = 1; i <= n; ++ i) {
if(dist[node][i] > lim)
continue;
if(!match[i] || pairUp(match[i])) {
match[i] = node;
return 1;
}
}
return 0;
}
int cuplaj () {
memset(match, 0, sizeof(match));
int i, ans;
ans = 0;
for(i = 1; i <= n; ++ i) {
memset(vis, 0, sizeof(vis));
ans += pairUp(i);
}
return ans;
}
double bs (double left, double right) {
double last;
int step;
for(step = 1; step <= 60; ++ step) {
lim = (left + right) * 0.5;
if(cuplaj() == n) {
last = lim;
right = lim;
}
else
left = lim;
}
return last;
}
double sqr (double x) {
return x * x;
}
int main() {
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
int i, j;
scanf("%d", &n);
for(i = 1; i <= n; ++ i)
soldat[i] = read();
for(i = 1; i <= n; ++ i)
adapost[i] = read();
for(i = 1; i <= n; ++ i)
for(j = 1; j <= n; ++ j)
dist[i][j] = sqrt(sqr(soldat[i].x - adapost[j].x) + sqr(soldat[i].y - adapost[j].y));
printf("%lf 0\n", (double)bs(0, 5000));
return 0;
}