Pagini recente » Cod sursa (job #2784573) | Cod sursa (job #474191) | Cod sursa (job #812290) | Cod sursa (job #1523297) | Cod sursa (job #711138)
Cod sursa(job #711138)
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
#define punct pair <double, double>
#define nmax 410
#define lmax 810
#define eps 0.001
#define x first
#define y second
#define inf 1<<30
punct s[nmax], a[nmax];
vector <int> g[lmax];
queue <int> q;
double cost[lmax][lmax], ans, smin, sum, d[lmax];
int n, c[lmax][lmax], f[lmax][lmax], u[lmax], t[lmax], src, dst;
double dist (punct a, punct b)
{
return sqrt((a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y));
}
void graph (double cmax)
{
int i, j;
for (i=0; i<=dst; i++) g[i].erase(g[i].begin(), g[i].end());
for (i=1; i<=n; i++)
{
g[src].push_back (i);
g[i].push_back (src);
c[src][i]=1;
}
for (i=1; i<=n; i++)
{
g[n+i].push_back (dst);
g[dst].push_back (n+i);
c[n+i][dst]=1;
}
for (i=1; i<=n; i++)
for (j=n+1; j<dst; j++)
if (cost[i][j]<=cmax)
{
g[i].push_back (j);
g[j].push_back (i);
c[i][j]=1;
}
}
double bellman_ford()
{
int i, nod, vec, j;
for (i=0; i<=dst; i++) d[i]=inf;
q.push (src);
d[src] = 0;
u[src] = 1;
while (!q.empty())
{
nod = q.front();
q.pop();
u[nod] = 0;
for (i=0; i<g[nod].size(); i++)
{
vec = g[nod][i];
if (f[nod][vec] != c[nod][vec])
if (cost[nod][vec] + d[nod] < d[vec])
{
d[vec] = cost[nod][vec] + d[nod];
t[vec] = nod;
if (!u[vec])
{
q.push(vec);
u[vec]=1;
}
}
}
}
return d[dst];
}
int cuplaj (double cmax)
{
int fm, nod, cnt=0, i, j;
for (i=0; i<=dst; i++)
{
t[i]=u[i]=0;
for (j=0; j<=dst; j++) f[i][j]=c[i][j]=0;
}
graph (cmax);
double x;
sum = 0;
while ((x = bellman_ford()) != inf)
{
fm = 10;
nod = dst;
while (nod)
{
fm = min (fm, c[t[nod]][nod] - f[t[nod]][nod]);
nod = t[nod];
}
nod = dst;
while (nod)
{
f[t[nod]][nod] += fm;
f[nod][t[nod]] -=fm;
nod=t[nod];
}
sum += x;
cnt += fm;
}
return cnt;
}
void search (double lo, double hi)
{
double m;
while (lo+eps < hi)
{
m = (lo+hi) /2;
if (cuplaj (m)==n)
{
ans = m;
smin = sum;
hi=m;
} else lo=m;
}
}
int main()
{
freopen("adapost.in","r",stdin);
freopen("adapost.out","w",stdout);
scanf("%d", &n);
int i, j;
double x, y, dmax=0;
for (i=1; i<=n; i++)
{
scanf ("%lf %lf", &x, &y);
s[i] = make_pair (x, y);
}
for (i=1; i<=n; i++)
{
scanf ("%lf %lf", &x, &y);
a[i] = make_pair (x, y);
}
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
{
cost[i][n+j] = dist (s[i], a[j]);
cost[n+j][i] = - cost[i][n+j];
if (cost[i][n+j] > dmax) dmax=cost[i][n+j];
}
src=0;
dst=n+n+1;
search (0, dmax);
printf ("%lf %lf\n", ans, smin);
}