Pagini recente » Cod sursa (job #2482151) | Cod sursa (job #2552196) | Cod sursa (job #907799) | Cod sursa (job #1164004) | Cod sursa (job #93147)
Cod sursa(job #93147)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <memory.h>
using namespace std;
const char iname[] = "adapost.in";
const char oname[] = "adapost.out";
#define MAX_N 400
#define sqr(z) ((z) * (z))
int n;
double S[MAX_N][2], A[MAX_N][2], D[MAX_N][MAX_N];
vector <double> V;
vector <int> G[MAX_N];
int l[MAX_N], r[MAX_N], u[MAX_N];
void read_in(void)
{
scanf("%d", &n);
for (int i = 0; i < n; ++ i)
scanf("%lf %lf", &S[i][0], &S[i][1]);
for (int i = 0; i < n; ++ i)
scanf("%lf %lf", &A[i][0], &A[i][1]);
}
int pairup(int n)
{
if (u[n])
return 0;
u[n] = 1;
vector <int>::iterator it;
for (it = G[n].begin(); it != G[n].end(); ++ it) {
if (!l[*it]) {
l[*it] = n;
r[n] = *it;
return 1;
}
}
for (it = G[n].begin(); it != G[n].end(); ++ it) {
if (pairup(l[*it])) {
l[*it] = n;
r[n] = *it;
return 1;
}
}
return 0;
}
int solve(const double max_cost)
{
int cnt = 0;
for (int i = 0; i < n; ++ i) {
l[i] = r[i] = u[i] = 0;
vector <int> ().swap(G[i]);
}
for (int s = 0; s < n; ++ s) {
for (int a = 0; a < n; ++ a) {
if (max_cost >= D[s][a])
G[s].push_back(a);
}
}
for (int i = 0; i < n; ++ i) {
if (!pairup(i)) {
memset(u, 0, sizeof(u));
cnt += pairup(i);
} else
cnt ++;
}
return cnt;
}
int main(void)
{
freopen(iname, "r", stdin);
freopen(oname, "w", stdout);
read_in();
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < n; ++ j) {
D[i][j] = sqrt(sqr(S[i][0] - A[j][0]) + sqr(S[i][1] - A[j][1]));
V.push_back(D[i][j]);
}
}
sort(V.begin(), V.end());
int delta, k;
for (delta = 1; delta < n * n; delta <<= 1) ;
for (k = 0; delta; delta >>= 1) {
if ((k + delta) < n * n && solve(V[k + delta]) < n)
k += delta;
}
if (solve(V[k]) < n)
k ++;
printf("%.5lf 0", V[k]);
return 0;
}