Pagini recente » Cod sursa (job #2513319) | Cod sursa (job #1303474) | Cod sursa (job #2298711) | Cod sursa (job #2630562) | Cod sursa (job #2507736)
#include <fstream>
#include <cmath>
#include <queue>
#include <iomanip>
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
const int NMax = 800, oo = 2e9;
double X[NMax + 5], Y[NMax + 5], Dist[NMax + 5][NMax + 5], Cost[NMax + 5];
int N, TT[NMax + 5], F[NMax + 5][NMax + 5], Sink, Sol, C[NMax + 5][NMax + 5];
bool InQ[NMax + 5];
vector <int> G[NMax + 5];
queue <int> Q;
double Euclid(double x1, double y1, double x2, double y2)
{
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
bool BellmanFord()
{
for(int i = 0; i <= Sink; i++)
Cost[i] = oo, TT[i] = -1, InQ[i] = false;
Q.push(0), Cost[0] = 0, InQ[0] = true;
while(!Q.empty())
{
int Node = Q.front(); Q.pop(), InQ[Node] = false;
for(int Next : G[Node])
if(F[Node][Next] != C[Node][Next] && Cost[Node] + Dist[Node][Next] < Cost[Next])
{
Cost[Next] = Cost[Node] + Dist[Node][Next];
TT[Next] = Node;
if(InQ[Next] == false)
Q.push(Next), InQ[Next] = true;
}
}
return (Cost[Sink] != oo);
}
double Flow(double DistMax)
{
for(int i = 0; i <= Sink; i++)
{
G[i].clear();
for(int j = 0; j <= Sink; j++)
F[i][j] = 0;
}
for(int i = 1; i <= N; i++)
G[0].push_back(i), G[i].push_back(0), C[0][i] = 1;
for(int i = N + 1; i <= 2 * N; i++)
G[i].push_back(Sink), G[Sink].push_back(i), C[i][Sink] = 1;
for(int i = 1; i <= N; i++)
for(int j = N + 1; j < Sink; j++)
{
C[i][j] = 1;
if(Dist[i][j] <= DistMax)
G[i].push_back(j), G[j].push_back(i);
}
double Ans = 0;
int FluxMax = 0;
while(BellmanFord())
{
int Fmin = oo;
for(int i = Sink; TT[i] != -1; i = TT[i])
Fmin = min(Fmin, C[TT[i]][i] - F[TT[i]][i]);
for(int i = Sink; TT[i] != -1; i = TT[i])
F[TT[i]][i] += Fmin, F[i][TT[i]] -= Fmin;
Ans += Fmin * Cost[Sink];
FluxMax += Fmin;
}
return ((FluxMax == N) ? Ans : -1);
}
int main()
{
fin >> N;
for(int i = 1; i <= N; i++)
fin >> X[i] >> Y[i];
for(int i = N + 1; i <= 2 * N; i++)
{
double x, y;
fin >> x >> y;
for(int soldier = 1; soldier <= N; soldier++)
{
Dist[soldier][i] = Euclid(x, y, X[soldier], Y[soldier]);
Dist[i][soldier] = -Dist[soldier][i];
}
}
Sink = 2 * N + 1;
for(int step = (1 << 24); step > 0; step >>= 1)
{
if(Flow((Sol + step) / 10000.0) == -1)
Sol += step;
}
fout << fixed << setprecision(4) << (Sol + 1) / 10000.0 << " " << Flow((Sol + 1) / 10000.0) << '\n';
fin.close();
fout.close();
return 0;
}