Pagini recente » Cod sursa (job #2261432) | Cod sursa (job #462756) | Cod sursa (job #208469) | Cod sursa (job #2633044) | Cod sursa (job #402641)
Cod sursa(job #402641)
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
#define x first
#define y second
#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)
const int MAX_N = 805;
const double INF = 0x3f3f3f3f;
int nr, N, M, C[MAX_N], R[MAX_N], P, U, Cap[MAX_N][MAX_N], F[MAX_N][MAX_N], T[MAX_N];
pair <double, double> S[MAX_N], A[MAX_N];
double L[MAX_N][MAX_N], E[MAX_N * MAX_N], Cost[MAX_N][MAX_N], D[MAX_N];
char viz[MAX_N];
vector <int> G[MAX_N];
inline double dist(pair <double, double> &a, pair <double, double> &b)
{
double dx = (a.x - b.x) * (a.x - b.x);
double dy = (a.y - b.y) * (a.y - b.y);
return sqrt(dx + dy);
}
void citire()
{
scanf("%d\n", &N);
for(int i = 1; i <= N; ++i)
scanf("%lf %lf\n", &S[i].x, &S[i].y);
for(int i = 1; i <= N; ++i)
scanf("%lf %lf\n", &A[i].x, &A[i].y);
for(int i = 1; i <= N; ++i)
{
for(int j = 1; j <= N; ++j)
{
L[i][j] = dist(S[i], A[j]);
E[++M] = L[i][j];
}
}
}
bool pairup(int nod)
{
if(viz[nod]) return 0;
viz[nod] = 1;
foreach(G[nod])
if(!R[*it])
{
C[nod] = *it;
R[*it] = nod;
return 1;
}
foreach(G[nod])
if(pairup(R[*it]))
{
C[nod] = *it;
R[*it] = nod;
return 1;
}
return 0;
}
inline bool cuplaj(double x)
{
for(int i = 1; i <= N; ++i)
{
G[i].clear();
for(int j = 1; j <= N; ++j)
if(x >= L[i][j])
G[i].push_back(j);
}
memset(C, 0, sizeof C);
memset(R, 0, sizeof R);
bool ok = 1;
while(ok)
{
ok = 0;
memset(viz, 0, sizeof viz);
for(int i = 1; i <= N; ++i)
if(!C[i])
ok |= pairup(i);
}
for(int i = 1; i <= N; ++i)
if(!C[i])
return 0;
return 1;
}
struct cmp
{
bool operator()(const int &a, const int &b) const
{
return D[a] > D[b];
}
};
inline bool dijkstra()
{
priority_queue <int, vector <int>, cmp> Q;
memset(viz, 0, sizeof viz);
for(int i = 1; i <= U; ++i)
D[i] = INF;
D[P] = 0;
Q.push(P);
viz[P] = 1;
while(!Q.empty())
{
int nod = Q.top();
Q.pop();
viz[nod] = 0;
foreach(G[nod])
{
if((D[*it] > D[nod] + Cost[nod][*it]) && (Cap[nod][*it] > F[nod][*it]))
{
D[*it] = D[nod] + Cost[nod][*it];
T[*it] = nod;
if(viz[*it]) continue;
viz[*it] = 1;
Q.push(*it);
}
}
}
return (D[U] != INF);
}
double flux(double x)
{
P = 0, U = 2*N+1;
for(int i = 1; i <= N; ++i)
{
G[i].clear();
for(int j = 1; j <= N; ++j)
if(L[i][j] <= x)
{
Cap[i][j+N] = 1;
Cost[i][j+N] = L[i][j];
Cost[j+N][i] = -L[i][j];
G[i].push_back(j+N);
G[j+N].push_back(i);
}
}
for(int i = 1; i <= N; ++i)
{
Cap[P][i] = 1;
G[i].push_back(P);
G[P].push_back(i);
Cap[i+N][U] = 1;
G[i+N].push_back(U);
G[U].push_back(i+N);
}
double flow = 0.0;
while(dijkstra())
{
for(int i = U; i; i = T[i])
F[T[i]][i]++,
F[i][T[i]]--;
flow += D[U];
}
return flow;
}
int main()
{
freopen("adapost.in", "rt", stdin);
freopen("adapost.out", "wt", stdout);
citire();
sort(E+1, E+M+1);
int i = M;
for(int lg = (1 << 18); lg; lg >>= 1)
if(i - lg > 0 && cuplaj(E[i-lg]))
i -= lg;
printf("%.5lf %.5lf\n", E[i], flux(E[i]));
}