Pagini recente » Cod sursa (job #1573772) | Cod sursa (job #1767936) | Cod sursa (job #2000563) | Cod sursa (job #351720) | Cod sursa (job #907315)
Cod sursa(job #907315)
#include <fstream>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <queue>
#define N 1000
#define eps 0.001
#define oo 0x3f3f3f3f
using namespace std;
typedef struct{
double x, y;
} elem;
elem Ad[N], Sold[N];
bool inq[N], viz[N];
double l, m, d, cost, Vmax, Cost[N][N], Dist[N];
int C[N][N], S, D, n, prev[N];
queue<int>Q;
double get_dist(elem a, elem b)
{
double x = (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
x = sqrt((double)x);
return x;
}
bool 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] != oo;
}
bool DF(double 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 val - Cost[x][i] > eps and !viz[i])
{
viz[i] = 1;
prev[i] = x;
Q.push(i);
}
}
return viz[D];
}
bool not_good(double 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;
double val;
ifstream fi("adapost.in");
ofstream fo("adapost.out");
fi >> n;
S = 0; D = 2*n+1;
for(i = 1; i <= n; i++)
{
fi >> Sold[i].x >> Sold[i].y;
}
for(i = 1; i <= n; i++)
{
fi >> Ad[i].x >> Ad[i].y;
}
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];
}
l = 0; d = Vmax;
while(d - l > eps)
{
m = (l+d)/2;
if(not_good(m)) l = m; else d = m;
}
val = l;
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];
}
fo << setprecision(5) << fixed;
fo << val << " " << cost << "\n";
return 0;
}