Cod sursa(job #907208)
#include <fstream>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <queue>
#define N 1000
#define oo (1LL << 50)
using namespace std;
typedef struct{
int x, y;
} elem;
elem Ad[N], Sold[N];
bool inq[N], viz[N];
long long step, cost, Vmax, n, Cost[N][N], Dist[N];
int C[N][N], S, D, prev[N];
queue<int>Q;
long long get_dist(elem a, elem b)
{
long long x = (long long)(a.x - b.x)*(a.x - b.x) + (long long)(a.y - b.y)*(a.y - b.y);
x = (long long)sqrt(x);
return x;
}
int Bellman()
{
int i, x;
for(i = S; i <= D; i++) Dist[i] = oo;
Dist[S] = 0;
Q.push(S);
while(!Q.empty())
{
x = Q.front(); Q.pop();
inq[x] = 0;
for(i = 0; i <= D; ++i)
if(C[x][i] and Dist[i] > Dist[x] + Cost[x][i])
{
Dist[i] = Dist[x] + Cost[x][i];
prev[i] = x;
if(!inq[i])
{
inq[i] = 1;
Q.push(i);
}
}
}
return Dist[D];
}
bool DF(int val)
{
int x, i;
memset(viz, 0, sizeof(viz));
Q.push(S);
viz[S] = 1;
while(!Q.empty())
{
x = Q.front();
Q.pop();
for(i = 0; i <= D; i++)
if(C[x][i] and Cost[x][i] <= val and !viz[i])
{
viz[i] = 1;
prev[i] = x;
Q.push(i);
}
}
return viz[D];
}
bool not_good(int val)
{
int i, j, sol = 0;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
{
C[i][j+n] = 1;
C[j+n][i] = 0;
C[S][i] = 1;
C[i][S] = 0;
C[j+n][D] = 1;
C[D][j+n] = 0;
}
while(DF(val))
{
for(i = D; i != S; i = prev[i])
C[prev[i]][i]--, C[i][prev[i]]++;
sol++;
}
return sol < n;
}
int main()
{
int i, j, val;
double x, y;
ifstream fi("adapost.in");
ofstream fo("adapost.out");
fi >> n;
S = 0; D = 2*n+1;
for(i = 1; i <= n; i++)
{
fi >> x >> y;
Sold[i].x = x*10000;
Sold[i].y = y*10000;
}
for(i = 1; i <= n; i++)
{
fi >> x >> y;
Ad[i].x = x*10000;
Ad[i].y = y*10000;
}
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
{
Cost[i][j+n] = get_dist(Sold[i], Ad[j]);
Cost[j+n][i] = -Cost[i][j+n];
C[i][j+n] = 1;
C[S][i] = 1;
C[j+n][D] = 1;
if(Cost[i][j+n] > Vmax) Vmax = Cost[i][j+n];
}
for(step = 1; step <= Vmax; step <<= 1);
for(val = 0; step; step >>= 1)
if(val+step <= Vmax and not_good(val+step)) val += step;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
{
C[i][j+n] = 1;
C[j+n][i] = 0;
C[S][i] = 1;
C[i][S] = 0;
C[i][S] = 0;
C[j+n][D] = 1;
C[D][j+n] = 0;
}
while(Bellman())
{
for(i = D; i != S; i = prev[i])
C[prev[i]][i]--, C[i][prev[i]]++;
cost += Dist[D];
}
x = (double)val/10000; y = (double)cost/10000;
fo << setprecision(5) << fixed;
fo << x << " " << y << "\n";
return 0;
}