Pagini recente » Cod sursa (job #1371539) | Cod sursa (job #1154557) | Cod sursa (job #1180827) | Cod sursa (job #865044) | Cod sursa (job #203387)
Cod sursa(job #203387)
using namespace std;
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#define Nmax 402
struct punct { float x,y; };
struct distanta { float v; int a,b; };
int N;
int i,j,maxim;
float total;
vector<int> G[2*Nmax]; //graf
char R[2*Nmax][2*Nmax]; //capacitati
punct S[Nmax],A[Nmax];
int T[2*Nmax], Q[30*Nmax];
char is[2*Nmax];
float D[2*Nmax];
distanta dist[Nmax*Nmax];
int nrd;
void citire()
{
float d;
freopen("adapost.in","r",stdin);
scanf("%d",&N);
for (i=1; i<=N; ++i)
scanf("%f %f",&S[i].x,&S[i].y);
for (i=1; i<=N; ++i)
scanf("%f %f",&A[i].x,&A[i].y);
for (i=1; i<=N; ++i)
for (j=1; j<=N; ++j)
{
d = sqrt( (S[i].x-A[j].x)*(S[i].x-A[j].x) + (S[i].y-A[j].y)*(S[i].y-A[j].y) );
dist[++nrd].v = d;
dist[nrd].a = i;
dist[nrd].b = N+j;
}
}
int cmp(const distanta &A, const distanta &B)
{
return A.v < B.v;
}
void build()
{
//sursa la soldat
for (i=1; i<=N; ++i)
R[0][i] = 1, R[i][0] = 0;
//soldat la adapost
for (i=1; i<=N; ++i)
for (j=N+1; j<=2*N; ++j)
R[i][j] = 1, R[j][i] = 0;
//adapost la destinatie
for (i=N+1; i<=2*N; ++i)
R[i][2*N+1] = 1, R[2*N+1][i] = 0;
}
int bellman()
{
int nod, st=1, dr=0;
vector<int>::iterator it;
T[2*N+1] = 0;
for (i=1; i<=N; ++i)
if (R[0][i])
{
Q[++dr] = i;
is[i] = 1;
D[i] = T[i] =0;
}
else D[i] = 999999, is[i] = 0;
for (i=N+1; i<=2*N+1; ++i)
D[i] = 999999, is[i] = 0;
while (st<=dr)
{
nod = Q[st];
if (nod<=N)
for (it=G[nod].begin(); it<G[nod].end() && *it<=maxim; ++it)
if (R[nod][dist[*it].b] && D[nod] + dist[*it].v < D[dist[*it].b])
{
D[dist[*it].b] = D[nod] + dist[*it].v;
T[dist[*it].b] = nod;
if (!is[dist[*it].b]) Q[++dr] = dist[*it].b, is[Q[dr]]=1;
}
if (nod>N)
{
if (R[nod][2*N+1] && D[nod]<D[2*N+1])
D[2*N+1] = D[nod], T[2*N+1] = nod;
for (it=G[nod].begin(); it<G[nod].end() && *it<=maxim; ++it)
if (R[nod][dist[*it].a] && D[nod] - dist[*it].v < D[dist[*it].a])
{
D[dist[*it].a] = D[nod] - dist[*it].v;
T[dist[*it].a] = nod;
if (!is[dist[*it].a]) Q[++dr] = dist[*it].a, is[Q[dr]]=1;
}
}
++st;
is[nod] = 0;
}
return T[2*N+1];
}
int bfs()
{
int nod, st=1, dr=0;
vector<int>::iterator it;
memset(T,0,sizeof(T));
for (i=1; i<=N; ++i)
if (R[0][i])
{
Q[++dr] = i;
T[i] = 0;
}
while (st<=dr)
{
nod = Q[st];
if (nod<=N)
for (it=G[nod].begin(); it<G[nod].end() && *it<=maxim; ++it)
if (R[nod][dist[*it].b] && !T[dist[*it].b])
{
Q[++dr] = dist[*it].b;
T[Q[dr]] = nod;
}
if (nod>N)
{
if (R[nod][2*N+1])
{ T[2*N+1] = nod; return nod; }
for (it=G[nod].begin(); it<G[nod].end() && *it<=maxim; ++it)
if (R[nod][dist[*it].a] && !T[dist[*it].a])
{
Q[++dr] = dist[*it].a;
T[Q[dr]] = nod;
}
}
++st;
}
return T[2*N+1];
}
int match()
{
int nr = 0, nod;
while ( bfs() )
{
++nr;
nod = 2*N+1;
while ( nod )
{
R[nod][T[nod]]=1, R[T[nod]][nod]=0;
nod = T[nod];
}
}
return nr;
}
void match2()
{
int nod;
total = 0;
while ( bellman() )
{
nod = 2*N+1;
total += D[nod];
nod = 2*N+1;
while ( nod )
{
R[nod][T[nod]]=1, R[T[nod]][nod]=0;
nod = T[nod];
}
}
}
void cauta()
{
int m=0, p=1;
while ( (p<<1) <= nrd ) p <<= 1;
while (p)
{
maxim = m+p;
build();
if (match() < N) m+=p;
p >>= 1;
while (m+p > nrd) p>>=1;
}
maxim=m+1;
build();
match2();
freopen("adapost.out","w",stdout);
printf("%.5f %.5f\n", dist[maxim].v, total);
fclose(stdout);
}
int main()
{
citire();
sort(dist+1, dist+nrd+1, cmp);
//construieste grafu
for (i=1; i<=nrd; ++i)
{
G[ dist[i].a ].push_back(i);
G[ dist[i].b ].push_back(i);
}
cauta();
return 0;
}