Pagini recente » Cod sursa (job #569326) | Cod sursa (job #259962) | Cod sursa (job #1395935) | Cod sursa (job #2756124) | Cod sursa (job #298303)
Cod sursa(job #298303)
#include <stdio.h>
#include <math.h>
#define N 403
using namespace std;
struct pct
{
double x,y;
}s[N],s1[N];
double infinit=1000000;
double dist[2*N+2][2*N+2];
double C[N];
double rez,Fl;
int cap[2*N+2][2*N+2];
int tati[2*N+2];
int viz[2*N+2];
int Q[2*N+2];
int inc,sf,n;
int S=0,D;
double distanta(pct a,pct b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void citire()
{
freopen ("adapost.in","r",stdin);
freopen ("adapost.out","w",stdout);
scanf ("%d",&n);
D=2*n+1;
for (int i=1;i<=n;i++)
scanf ("%lf %lf",&s[i].x,&s[i].y);
for (int i=1;i<=n;i++)
scanf ("%lf %lf",&s1[i].x,&s1[i].y);
for (int i=1;i<=n;i++)
{
cap[0][i]=1;
for (int j=1;j<=n;j++)
{
cap[i][j+n]=1;
dist[i][j+n]=distanta(s[i],s1[j]);
dist[j+n][i]=-dist[i][j+n];
cap[j+n][D]=1;
}
}
}
void bell()
{
for (int i=1;i<=2*n+1;i++)
C[i]=infinit;
int nod;
double cc;
C[S]=0;
inc=0;
sf=1;
Q[0]=S;
viz[S]=1;
while (inc<sf)
{
nod=Q[inc++];
viz[nod]=0;
cc=C[nod];
for (int i=1;i<=2*n+1;i++)
if (cap[nod][i] && C[i]>C[nod]+dist[nod][i])
{
tati[i]=nod;
C[i]=C[nod]+dist[nod][i];
if (!viz[i])
{
viz[i]=1;
Q[sf++]=i;
}
}
}
}
int mini(int a,int b)
{
return a>b?b:a;
}
void calc()
{
Fl=-1;
int poz;
int flux;
bell();
while (C[D]!=infinit)
{
poz=D;
flux=2;
while (poz!=S)
{
flux=mini(flux,cap[tati[poz]][poz]);
poz=tati[poz];
}
poz=D;
while (poz!=S)
{
cap[poz][tati[poz]]+=flux;
cap[tati[poz]][poz]-=flux;
poz=tati[poz];
}
rez+=C[D];
bell();
}
}
int main ()
{
citire();
calc();
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (cap[i][j+n]==0 && dist[i][j+n]>Fl)
Fl=dist[i][j+n];
printf("%lf %lf\n",Fl,rez);
return 0;
}