Pagini recente » Cod sursa (job #1064797) | Cod sursa (job #2930351) | Cod sursa (job #2139053) | Cod sursa (job #1179339) | Cod sursa (job #533010)
Cod sursa(job #533010)
#include <fstream>
#include <math.h>
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
#include <vector>
#include <queue>
#define maxn 805
#define maxm 160005
#define oo 200000000
#define pb push_back
int i,j,N,nrM,srs,dest,k,flmin,m,st,dr,nrC;
struct coord { double x,y; } s[maxn],ad[maxn];
double M[maxm],Cost[maxn][maxn],D[maxn];
double MinDist,x,R,Rmax;
vector <int> A[maxn];
queue <int> Q;
int C[maxn][maxn],id[maxm],from[maxn],v[maxn];
inline double min(double a, double b)
{
return a<b ? a : b;
}
void citire()
{
fin >> N;
for(i=1;i<=N;i++)
fin >> s[i].x >> s[i].y;
for(i=1;i<=N;i++)
fin >> ad[i].x >> ad[i].y;
}
void constr()
{
double val;
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
{
val=sqrt(pow(s[i].x-ad[j].x,2)+pow(s[i].y-ad[j].y,2));
M[++nrM]=val;
A[i].pb(j+N); A[j+N].pb(i);
C[i][j+N]=1; Cost[i][j+N]=val; Cost[j+N][i]=-val;
}
srs=0; dest=2*N+1;
for(i=1;i<=N;i++)
{
A[srs].pb(i); A[i].pb(srs);
C[srs][i]=1;
A[i+N].pb(dest); A[dest].pb(i+N);
C[i+N][dest]=1;
}
}
void sortare()
{
for(i=1;i<=nrM;i++) id[i]=i;
int aux;
for(i=1;i<=nrM-1;i++)
for(j=i+1;j<=nrM;j++)
if(M[id[i]]>M[id[j]])
{
aux=id[i];
id[i]=id[j];
id[j]=aux;
}
}
int BF(double x)
{
for(i=1;i<=dest;i++) { D[i]=oo; v[i]=0; }
Q.push(srs); D[srs]=0; v[srs]=1;
for(;!Q.empty();Q.pop())
{
k=Q.front();
for(i=0;i<(int)A[k].size();i++)
if(Cost[k][A[k][i]]<=x && C[k][A[k][i]]>0)
if(D[k]+Cost[k][A[k][i]]<D[A[k][i]])
{
D[A[k][i]]=D[k]+Cost[k][A[k][i]];
from[A[k][i]]=k;
if(!v[A[k][i]])
{
Q.push(A[k][i]);
v[A[k][i]]=1;
}
}
v[k]=0;
}
return D[dest]<oo;
}
int flux(int m)
{
x=M[id[m]]; R=0; nrC=0;
for(i=1;i<=N;i++)
{
for(j=1;j<=N;j++)
{
C[i][j+N]=1;
C[j+N][i]=0;
}
C[srs][i]=1; C[i][srs]=0;
C[i+N][dest]=1; C[dest][i+N]=0;
}
while( BF(x) )
{
flmin=oo;
for(k=dest;k!=srs;k=from[k])
flmin=min(flmin,C[from[k]][k]);
for(k=dest;k!=srs;k=from[k])
{
C[from[k]][k]-=flmin;
C[k][from[k]]+=flmin;
}
R+=flmin*D[dest];
nrC+=flmin;
}
return nrC==N;
}
void cb(int st, int dr)
{
m=st+(dr-st)/2; MinDist=oo;
while(st<=dr)
{
if( flux(m) )
{
dr=m;
MinDist=M[id[m]]; Rmax=R;
}
else
st=m+1;
if(st==m && st==dr) break;
m=st+(dr-st)/2;
}
}
int main()
{
citire();
constr();
sortare();
cb(1,nrM);
fout.precision(7);
fout << MinDist << '\n';
fout << Rmax;
}