Pagini recente » Cod sursa (job #2771776) | Cod sursa (job #1645018) | Cod sursa (job #343892) | Cod sursa (job #2562809) | Cod sursa (job #71064)
Cod sursa(job #71064)
using namespace std;
#include<fstream>
#include<stdio.h>
#include<math.h>
#define Nmax 405
#define inf 100000000.0
int N;
double cxad[Nmax],cyad[Nmax],cxsol[Nmax],cysol[Nmax],dist[Nmax*Nmax],init[Nmax][Nmax];
double cost[2*Nmax][2*Nmax],flux[2*Nmax];
char cap[2*Nmax][2*Nmax];
int heap[2*Nmax],nh,ph[2*Nmax],ant[2*Nmax];
ifstream fin("adapost.in");
FILE *fout=fopen("adapost.out","w");
double flow(double Vmax)
{
int i,j;
//initializare
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
{
cost[j+N][i]=0.0;
cap[j+N][i]=0;
if(init[i][j] <= Vmax)
{
cost[i][j+N]=init[i][j];
cap[i][j+N]=1;
}
else
{
cost[i][j+N]=0.0;
cap[i][j+N]=0;
}
}
for(i=1;i<=N;i++)
{
cap[0][i]=cap[i+N][2*N+1]=1;
cap[i][0]=cap[2*N+1][i+N]=0;
cost[0][i]=cost[i+N][2*N+1]=0.0;
cost[i][0]=cost[2*N+1][i+N]=0.0;
}
int X,dest=2*N+1,aux,ori=0;
double F=0.0;
while(1)
{
nh=2*N+2;
for(i=0;i<=2*N+1;i++)
{
flux[i]=inf;
heap[i+1]=i;
ph[i]=i+1;
}
flux[0]=0.0;
while(heap[1] != dest && flux[heap[1]] < inf)
{
X=heap[1];
//intersc 1 cu nh
aux=heap[1];
heap[1]=heap[nh];
heap[nh]=aux;
ph[heap[1]]=1;
ph[heap[nh]]=nh;
nh--;
i=1;
while(1)
{
j=i<<1;
if(j>nh) break;
if(j+1<=nh && flux[heap[j+1]] < flux[heap[j]]) j++;
if(flux[heap[i]] <= flux[heap[j]]) break;
aux=heap[i];
heap[i]=heap[j];
heap[j]=aux;
ph[heap[i]]=i;
ph[heap[j]]=j;
i=j;
}
if(X<=N && X>0)
{
for(i=N+1;i<=2*N;i++)
if(cap[X][i] && flux[i] > flux[X] + cost[X][i])
{
flux[i]=flux[X]+cost[X][i];
ant[i]=X;
//refacere heap
j=ph[i];
while(j/2 && flux[heap[j/2]] > flux[heap[j]] )
{
aux=heap[j/2];
heap[j/2]=heap[j];
heap[j]=aux;
ph[heap[j/2]]=j/2;
ph[heap[j]]=j;
j>>=1;
}
}
}
else
{
for(i=1;i<=N;i++)
if(cap[X][i] && flux[i] > flux[X] + cost[X][i])
{
flux[i]=flux[X]+cost[X][i];
ant[i]=X;
//refacere heap
j=ph[i];
while(j/2 && flux[heap[j/2]] > flux[heap[j]] )
{
aux=heap[j/2];
heap[j/2]=heap[j];
heap[j]=aux;
ph[heap[j/2]]=j/2;
ph[heap[j]]=j;
j>>=1;
}
}
if(cap[X][dest] && flux[dest]> flux[X] + cost[X][dest])
{
flux[dest]=flux[X]+cost[X][dest];
ant[dest]=X;
//refacere heap
j=ph[dest];
while(j/2 && flux[heap[j/2]] > flux[heap[j]] )
{
aux=heap[j/2];
heap[j/2]=heap[j];
heap[j]=aux;
ph[heap[j/2]]=j/2;
ph[heap[j]]=j;
j>>=1;
}
}
}
}
if(flux[heap[1]] == inf)
if(ori==N)
return F;
else
return -1.0;
i=dest;
while(i>0)
{
cap[ant[i]][i]=0;
cap[i][ant[i]]=1;
cost[i][ant[i]] = -cost[ant[i]][i];
cost[ant[i]][i]=0.0;
i=ant[i];
}
F+=flux[dest];
ori++;
}
}
int main()
{
int i,j,k;
double dx,dy,val,aux;
fin>>N;
for(i=1;i<=N;i++)
fin>>cxsol[i]>>cysol[i];
for(i=1;i<=N;i++)
fin>>cxad[i]>>cyad[i];
k=0;
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
{
dx=cxsol[i] - cxad[j];
dy=cysol[i] - cyad[j];
init[i][j]= sqrt(dx*dx + dy*dy);
dist[++k]=init[i][j];
}
for(i=1;i<=N*N;i++)
{
j=i;
while(j/2 && dist[j/2] < dist[j])
{
aux=dist[j/2];
dist[j/2]=dist[j];
dist[j]=aux;
j/=2;
}
}
i=N*N;
while(i>1)
{
aux=dist[1];
dist[1]=dist[i];
dist[i]=aux;
i--;
j=1;
while(1)
{
k=j*2;
if(k>i) break;
if(k+1<=i && dist[k+1] > dist[k]) k++;
if(dist[j] >= dist[k]) break;
aux=dist[j];
dist[j]=dist[k];
dist[k]=aux;
j=k;
}
}
int li,lf,mij;
double distMin,totalMin;
li=1;lf=N*N;
for(li=1;li<=N*N;li++)
{
val=flow(dist[li]);
if(val >= 0.0)
{
distMin=dist[li];
totalMin=val;
break;
}
}
/*
while(li<=lf)
{
mij=(li+lf)>>1;
val=flow(dist[mij]);
if( val >= 0.0 )
{
distMin= dist[mij];
totalMin= val;
lf=mij-1;
}
else
li=mij+1;
}
*/
fprintf(fout,"%f %f\n",distMin,totalMin);
fin.close();
fclose(fout);
return 0;
}