Pagini recente » Cod sursa (job #1793628) | Cod sursa (job #3289175) | Cod sursa (job #1233449) | Cod sursa (job #2915372) | Cod sursa (job #907219)
Cod sursa(job #907219)
#include <fstream>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <queue>
#define N 1000
#define oo 0x3f3f3f3f
using namespace std;
typedef struct{
double x, y;
} elem;
elem Ad[N], Sold[N];
bool inq[N], viz[N];
int step, cost, Vmax, n, Cost[N][N], Dist[N];
int C[N][N], S, D, prev[N];
queue<int>Q;
int 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);
int y = (int)((double)x * 10000);
return y;
}
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(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 >> 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];
}
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;
}