Pagini recente » Cod sursa (job #3037916) | Cod sursa (job #1433048) | Cod sursa (job #2752692) | Cod sursa (job #2352940) | Cod sursa (job #17464)
Cod sursa(job #17464)
#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 410
#define INF 1000000000
#define eps 0.0001
int N;
double xx[NMAX];
double yy[NMAX];
double xxa[NMAX];
double yya[NMAX];
pair <double, int> leg[NMAX][NMAX];
vector <pair<int, double> > lg[NMAX * 2];
int cap[NMAX * 2][NMAX * 2];
char viz[NMAX];
int st[NMAX];
int pair_up(int x, double max)
{
if (viz[x]) return 0;
viz[x] = 1;
for (int i = 1; i <= N && leg[x][i].first <= max; i++)
if (!st[ leg[x][i].second ] || pair_up(st[ leg[x][i].second ], max)) {
st[ leg[x][i].second ] = x;
return 1;
}
return 0;
}
int cuplaj(double max)
{
int i;
memset(viz, 0, sizeof(viz));
memset(st, 0, sizeof(st));
for (i = 1; i <= N; i++)
if (!pair_up(i, max)) {
memset(viz, 0, sizeof(viz));
pair_up(i, max);
}
int rez = 0;
for (i = 1; i <= N; i++) rez += st[i] > 0;
return rez;
}
int coada[NMAX * NMAX * 4];
double dist[NMAX * 2];
int pred[NMAX * 2];
char in_coada[NMAX * 2];
int bf()
{
memset(in_coada, 0, sizeof(viz));
int p, q, i, x, y;
for (i = 1; i <= 2 * N + 1; i++) dist[i] = INF;
p = q = 0;
coada[0] = 0;
vector <pair<int, double> > :: iterator it;
while (p <= q) {
x = coada[p];
p++;
in_coada[x] = 0;
for (it = lg[x].begin(); it != lg[x].end(); it++) {
y = (*it).first;
if (dist[x] + (*it).second < dist[y] && cap[x][y]) {
dist[y] = dist[x] + (*it).second;
pred[y] = x;
if (!in_coada[y]) coada[++q] = y, in_coada[y] = 1;
}
}
}
return dist[2 * N + 1] < INF;
}
double baga_flux_cu_cost(double max)
{
int i, cur, j;
// fac graful
for (i = 1; i <= N; i++) {
lg[0].push_back(make_pair(i, 0));
cap[0][i] = 1;
}
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++) {
if (leg[i][j].first <= max) {
lg[i].push_back(make_pair(leg[i][j].second + N, leg[i][j].first));
cap[i][leg[i][j].second + N] = 1;
lg[leg[i][j].second + N].push_back(make_pair(i, -leg[i][j].first));
}
}
for (i = 1; i <= N; i++) {
lg[i + N].push_back(make_pair(2 * N + 1, 0));
cap[i + N][2 * N + 1] = 1;
}
double rez = 0;
while (bf()) {
rez += dist[2 * N + 1];
cur = 2 * N + 1;
while (cur) {
cap[pred[cur]][cur]--;
cap[cur][pred[cur]]++;
cur = pred[cur];
}
}
return rez;
}
int main()
{
int i, j;
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; i++) scanf("%lf %lf", &xx[i], &yy[i]);
for (i = 1; i <= N; i++) scanf("%lf %lf", &xxa[i], &yya[i]);
for (i = 1; i <= N; i++) {
for (j = 1; j <= N; j++)
leg[i][j] = make_pair( sqrt( (xx[i] - xxa[j]) * (xx[i] - xxa[j]) + (yy[i] - yya[j]) * (yy[i] - yya[j]) ), j );
sort(leg[i] + 1, leg[i] + N + 1);
}
double step;
for (step = 1; step <= 1000; step *= 2);
// caut maximul minim
double rez = 0;
for (; step > 0.00001; step *= 0.5)
if (cuplaj(rez + step) < N)
rez += step;
printf("%lf %lf\n", rez, baga_flux_cu_cost(rez + eps));
fclose(stdin);
fclose(stdout);
return 0;
}