Pagini recente » Cod sursa (job #1312701) | Cod sursa (job #3145794) | Cod sursa (job #676172)
Cod sursa(job #676172)
#include <cmath>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define x first
#define y second
const double eps = 0.0001;
const int INF = 0x3f3f3f3f;
int N;
pair<double, double> A[402], B[402];
bool inQ[802];
int C[802][802], F[802][802], T[802], times;
double sumdist, D[802];
queue<int> Q;
inline double pow2(double val)
{
return val * val;
}
inline double getDistance(int i1, int i2)
{
return sqrt(pow2(A[i1].x - B[i2].x) + pow2(A[i1].y - B[i2].y));
}
inline double psDistance(int i1, int i2)
{
if (i1 == 0 || i1 == 2 * N + 1 || i2 == 0 || i2 == 2 * N + 1) return 0;
if (i2 > N) return getDistance(i1, i2 - N);
return -getDistance(i2, i1 - N);
}
bool findPath()
{
memset(inQ, 0, sizeof(inQ));
while (!Q.empty()) Q.pop();
for (int i = 0; i <= 2 * N + 1; ++i)
D[i] = INF;
Q.push(0);
inQ[0] = true;
D[0] = 0;
while (!Q.empty())
{
int now = Q.front();
Q.pop();
inQ[now] = false;
for (int i = 0; i <= 2 * N + 1; ++i)
if (C[now][i] > F[now][i] && D[now] + psDistance(now, i) < D[i])
{
D[i] = D[now] + psDistance(now, i);
T[i] = now;
if (!inQ[i])
{
inQ[i] = true;
Q.push(i);
}
}
}
if (D[2 * N + 1] == INF) return false;
//printf("%d\n", times);
++times;
for (int i = 2 * N + 1; i != 0; i = T[i])
{
//printf("%d %d\n", T[i], i);
++F[T[i]][i], --F[i][T[i]];
sumdist += psDistance(T[i], i);
}
return true;
}
void clearAll()
{
times = 0;
sumdist = 0;
memset(C, 0, sizeof(C));
memset(F, 0, sizeof(F));
}
bool ok(double now)
{
clearAll();
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j)
if (now - getDistance(i, j) > eps)
C[i][N + j] = 1;
for (int i = 1; i <= N; ++i)
{
C[0][i] = 1;
C[N + i][2 * N + 1] = 1;
}
while (findPath());
if (times == N)
return true;
return false;
}
int main()
{
ifstream fin("adapost.in");
ofstream fout("adapost.out");
fin >> N;
for (int i = 1; i <= N; ++i)
fin >> A[i].x >> A[i].y;
for (int i = 1; i <= N; ++i)
fin >> B[i].x >> B[i].y;
double lim1 = 0, lim2 = 2000;
while (lim2 - lim1 >= eps)
{
double mid = (lim1 + lim2) / 2;
bool resultnow = ok(mid);
if (resultnow)
lim2 = mid;
else
lim1 = mid;
}
ok(lim2);
fout << fixed << setprecision(4) << lim2;
fout << ' ';
fout << fixed << setprecision(4) << sumdist;
fout << '\n';
fin.close();
fout.close();
}