Pagini recente » Cod sursa (job #2909640) | Cod sursa (job #2200983) | Cod sursa (job #3240016) | Cod sursa (job #575424) | Cod sursa (job #1015733)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#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 flux, step, n;
double Cost[N][N], Dist[N], sol, cost;
int C[N][N], S, D, prec[N];
queue<int>Q;
vector<double>distances;
int nd;
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(double val)
{
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] and Cost[x][i] <= val)
{
Dist[i] = Dist[x] + Cost[x][i];
prec[i] = x;
if(!inq[i])
{
inq[i] = 1;
Q.push(i);
}
}
}
return Dist[D] != oo;
}
bool BF(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 Cost[x][i] <= val and !viz[i])
{
viz[i] = 1;
prec[i] = x;
Q.push(i);
}
}
return viz[D];
}
bool not_good(double val)
{
int i;
while(BF(val))
{
for(i = D; i != S; i = prec[i])
C[prec[i]][i]--, C[i][prec[i]]++;
flux++;
}
return flux < n;
}
int main()
{
int i, j;
//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];
distances.push_back(Cost[i][j+n]);
C[i][j+n] = 1;
C[S][i] = 1;
C[j+n][D] = 1;
}
nd = distances.size();
sort(distances.begin(), distances.end());
for(i = 0; i < nd; i++)
if(!not_good(distances[i]))
{
sol = distances[i];
break;
}
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(sol))
// {
// for(i = D; i != S; i = prec[i])
// C[prec[i]][i]--, C[i][prec[i]]++;
// cost += Dist[D];
// }
fo << setprecision(5) << fixed;
fo << sol << " " << cost << "\n";
return 0;
}