Pagini recente » Cod sursa (job #3137880) | Cod sursa (job #2204339) | Cod sursa (job #700571) | Cod sursa (job #32727) | Cod sursa (job #343130)
Cod sursa(job #343130)
#include <cstdio>
#include <math.h>
#include <vector>
#include <cstring>
#include <algorithm>
#define maxn 805
#define inf 0x3f3f3f3f
using namespace std;
struct punct {
int x, y;
};
int n, i, j;
double aa, bb;
punct v[2 * maxn];
bool viz[2 * maxn], cup_st[2 * maxn], cup_dr[2 * maxn];
int dist_min, cost_min;
int dist[2 * maxn][2 * maxn];
int cb[maxn * maxn], nr;
int ok;
vector <int> g[maxn];
inline int distanta(punct a, punct b) {
return (int) sqrt(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y));
}
inline void build_graf(int dmax) {
int i, j;
for (i = 1; i <= 2 * n; i++)
g[i].clear();
for (i = 1; i <= n; i++)
for (j = n + 1; j <= 2 * n; j++)
if (dist[i][j] <= dmax) {
g[i].push_back(j);
g[j].push_back(i);
}
}
inline int cupleaza(int nod, int pt) {
int i, fiu;
if (pt == 0) {
if (viz[nod])
return 0;
viz[nod] = 1;
for (i = 0; i < g[nod].size(); i++) {
fiu = g[nod][i];
if (!cup_dr[fiu]) {
cup_dr[fiu] = nod;
cup_st[nod] = fiu;
return 1;
}
}
for (i = 0; i < g[nod].size(); i++) {
fiu = g[nod][i];
if (cup_dr[fiu]) {
if (cupleaza(fiu, 1)) {
cup_st[nod] = fiu;
cup_dr[fiu] = nod;
return 1;
}
}
}
return 0;
}
else {
if (cup_dr[nod])
return cupleaza(cup_dr[nod], 0);
else
return 1;
}
}
inline bool posibil(int dmax) {
int i, nr = 0;
build_graf(dmax);
ok = 1;
memset(cup_st, 0, sizeof(cup_st));
memset(cup_dr, 0, sizeof(cup_dr));
while (ok) {
ok = 0;
memset(viz, 0, sizeof(viz));
for (i = 1; i <= n; i++) {
if (!cup_st[i])
if (cupleaza(i, 0)) {
nr ++;
ok = 1;
}
}
}
if (nr == n)
return true;
return false;
}
void bsearch(int left, int right) {
int m;
while (left <= right) {
m = (left + right) / 2;
if (posibil(cb[m])) {
dist_min = min(dist_min, cb[m]);
right = m - 1;
}
else
left = m + 1;
}
}
inline void afis(int nr) {
printf("%d.", nr / 100000);
int aux = nr % 100000;
if (aux)
while (aux < 10000) {
printf("0");
aux *= 10;
}
printf("%d ", nr % 100000);
}
int main() {
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
scanf("%d", &n);
for (i = 1; i <= 2 * n; i++) {
scanf("%lf%lf", &aa, &bb);
v[i].x = (int) (aa * 100000);
v[i].y = (int) (bb * 100000);
}
dist_min = inf;
for (i = 1; i <= n; i++)
for (j = i + 1; j <= 2 * n; j++) {
dist[i][j] = distanta(v[i], v[j]);
dist[j][i] = -dist[i][j];
nr++;
cb[nr] = dist[i][j];
}
sort(cb + 1, cb + nr + 1);
bsearch(1, nr);
afis(dist_min);
return 0;
}