Pagini recente » Cod sursa (job #388356) | Cod sursa (job #1930535) | Cod sursa (job #1492978) | Cod sursa (job #1815942) | Cod sursa (job #1401254)
#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;
pair <int, int> soldat[NMAX], adapost[NMAX];
int n, left[NMAX];
bool vis[NMAX];
LL lim, dist[NMAX][NMAX];
pair <int, int> read() {
char ln[20];
int x, y, i;
gets(ln);
i = x = 0;
while(ln[i] != ' ') {
if(ln[i] >= '0' && ln[i] <= '9')
x = x * 10 + ln[i] - '0';
++ i;
}
++ i;
y = 0;
while(ln[i]) {
if(ln[i] >= '0' && ln[i] <= '9')
y = y * 10 + ln[i] - '0';
++ i;
}
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(!left[i] || pairUp(left[i])) {
left[i] = node;
return 1;
}
}
return 0;
}
int cuplaj () {
memset(left, 0, sizeof(left));
int i, ans;
ans = 0;
for(i = 1; i <= n; ++ i) {
memset(vis, 0, sizeof(vis));
ans += pairUp(i);
}
return ans;
}
int bs (LL left, LL right) {
LL last;
right *= right;
while(left <= right) {
lim = (left + right) / 2;
if(cuplaj() >= n) {
last = lim;
right = lim - 1;
}
else
left = lim + 1;
}
return sqrt(last);
}
int main() {
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
int i, j, left, right;
scanf("%d\n", &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] = (soldat[i].x - adapost[j].x) * (soldat[i].x - adapost[j].x) + (soldat[i].y - adapost[j].y) * (soldat[i].y - adapost[j].y);
printf("%.3lf", (double)bs(0, 1e6) / 1000);
return 0;
}