Pagini recente » Cod sursa (job #1184191) | Cod sursa (job #2309480) | Cod sursa (job #2913572) | Cod sursa (job #947971) | Cod sursa (job #203354)
Cod sursa(job #203354)
using namespace std;
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define Nmax 512
struct punct { double x,y; };
int N;
int i,j;
double total;
double C[2*Nmax][2*Nmax]; //costuri
char R[2*Nmax][2*Nmax]; //capacitati
punct S[Nmax],A[Nmax];
int T[2*Nmax], Q[20*Nmax];
char is[2*Nmax];
double D[2*Nmax];
double dist[Nmax*Nmax];
int nrd;
void citire()
{
freopen("adapost.in","r",stdin);
scanf("%d",&N);
for (i=1; i<=N; ++i)
scanf("%lf %lf",&S[i].x,&S[i].y);
for (i=1; i<=N; ++i)
scanf("%lf %lf",&A[i].x,&A[i].y);
for (i=1; i<=N; ++i)
for (j=1; j<=N; ++j)
{
C[i][N+j] = 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) );
C[N+j][i] = - C[i][N+j];
dist[++nrd] = C[i][N+j];
}
}
void build(double maxim)
{
//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)
if (C[i][j] <= maxim)
R[i][j] = 1, R[j][i] = 0;
else R[i][j] = 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;
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] = 9999999, is[i] = 0;
for (i=N+1; i<=2*N+1; ++i)
D[i] = 99999999, is[i] = 0;
while (st<=dr)
{
nod = Q[st];
if (nod<=N)
for (i=N+1; i<=2*N; ++i)
if (R[nod][i] && D[nod] + C[nod][i] < D[i])
{
D[i] = D[nod] + C[nod][i];
T[i] = nod;
if (!is[i]) Q[++dr] = i, is[i]=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 (i=1; i<=N; ++i)
if (R[nod][i] && D[nod] + C[nod][i] < D[i])
{
D[i] = D[nod] + C[nod][i];
T[i] = nod;
if (!is[i]) Q[++dr] = i, is[i]=1;
}
}
++st;
is[nod] = 0;
}
return T[2*N+1];
}
int match()
{
int nr = 0, nod;
total = 0;
while ( bellman() )
{
++nr;
nod = 2*N+1;
while ( nod )
{
total += C[T[nod]][nod];
nod = T[nod];
}
nod = 2*N+1;
while ( nod )
{
R[nod][T[nod]]=1, R[T[nod]][nod]=0;
nod = T[nod];
}
}
return nr;
}
void cauta()
{
int m=0, p=1;
while ( (p<<1) <= nrd ) p <<= 1;
while (p)
{
build(dist[m+p]);
if (match() < N) m+=p;
p >>= 1;
while (m+p > nrd) p>>=1;
}
build(dist[m+1]);
match();
freopen("adapost.out","w",stdout);
printf("%.5lf %.5lf\n", dist[m+1], total);
fclose(stdout);
}
int main()
{
citire();
sort(dist+1, dist+nrd+1);
cauta();
return 0;
}