Pagini recente » Cod sursa (job #2807159) | Cod sursa (job #1032115) | Cod sursa (job #1370112) | Cod sursa (job #2876449) | Cod sursa (job #71068)
Cod sursa(job #71068)
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 q[Nmax*Nmax],ant[Nmax],soldat[2*Nmax];
char inq[2*Nmax];
int vec[Nmax][Nmax],nvec[Nmax],bfs[2*Nmax];
int x[Nmax*Nmax],y[Nmax*Nmax];
char viz[2*Nmax];
int nv=0;
ifstream fin("adapost.in");
FILE *fout=fopen("adapost.out","w");
double flow(double Vmax)
{
int i,j;
//initializare
for(i=1;i<=N;i++)
{
nvec[i]=0;
for(j=1;j<=N;j++)
{
cap[j+N][i]=0;
if(init[i][j] <= Vmax)
{
vec[i][++nvec[i]]=j+N;
cost[i][j+N]=init[i][j];
cost[j+N][i]=-init[i][j];
cap[i][j+N]=1;
}
else
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,ori=0,li,lf;
double F=0.0;
while(1)
{
for(i=1;i<=2*N+1;i++)
flux[i]=inf;
flux[0]=0.0;
li=1;lf=1;
q[1]=0;
inq[0]=1;
while(li<=lf)
{
X=q[li];
if(X<=N && X>0)
{
for(j=1;j<=nvec[X];j++)
{
i=vec[X][j];
if(cap[X][i] && flux[i] > flux[X] + cost[X][i] && flux[X] + cost[X][i] <= flux[dest])
{
flux[i]=flux[X]+cost[X][i];
ant[i]=X;
if(!inq[i])
{
q[++lf]=i;
inq[i]=1;
}
}
}
}
else
{
if(X==0)
{
for(i=1;i<=N;i++)
if(cap[X][i] && flux[i] > flux[X] + cost[X][i] && flux[X] + cost[X][i] <= flux[dest])
{
flux[i]=flux[X]+cost[X][i];
ant[i]=X;
if(!inq[i])
{
q[++lf]=i;
inq[i]=1;
}
}
}
else
{
i=soldat[X];
if(cap[X][i] && flux[i] > flux[X] + cost[X][i] && flux[X] + cost[X][i] <= flux[dest])
{
flux[i]=flux[X]+cost[X][i];
ant[i]=X;
if(!inq[i])
{
q[++lf]=i;
inq[i]=1;
}
}
if(cap[X][dest] && flux[dest]> flux[X] + cost[X][dest])
{
flux[dest]=flux[X]+cost[X][dest];
ant[dest]=X;
}
}
}
li++;
inq[X]=0;
}
if(flux[dest] == 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;
if(i>N && ant[i]<=N)
soldat[i]=ant[i];
i=ant[i];
}
F+=flux[dest];
ori++;
}
}
int simple_flow(int fin)
{
memset(nvec,0,sizeof nvec);
int i,F=0,li,lf,X,j;
for(i=1;i<=fin;i++)
{
vec[x[i]][ ++nvec[x[i]] ] =y[i];
cap[x[i]][y[i]]=1;
cap[y[i]][x[i]]=0;
}
for(i=1;i<=N;i++)
{
vec[0][++nvec[0]]=i;
cap[0][i]=1;
cap[i][0]=0;
cap[i+N][2*N+1]=1;
cap[2*N+1][i+N]=0;
}
while(F<N)
{
memset(inq,0,sizeof inq);
li=lf=1;
bfs[li]=0;
while(li<=lf)
{
X=bfs[li];
if(X<=N && X>0)
{
for(j=1;j<=nvec[X];j++)
{
i=vec[X][j];
if(cap[X][i] && !inq[i])
{
ant[i]=X;
bfs[++lf]=i;
inq[i]=1;
}
}
}
else
{
if(X==0)
{
for(i=1;i<=N;i++)
if(cap[X][i] && !inq[i])
{
ant[i]=X;
bfs[++lf]=i;
inq[i]=1;
}
}
else
{
i=soldat[X];
if(cap[X][i] && !inq[i])
{
ant[i]=X;
bfs[++lf]=i;
inq[i]=1;
}
if(cap[X][2*N+1])
{
ant[2*N+1]=X;
inq[2*N+1]=1;
break;
}
}
}
li++;
}
if(inq[2*N+1]==0) break;
F++;
i=2*N+1;
while(i>0)
{
cap[ant[i]][i]=0;
cap[i][ant[i]]=1;
if(i>N && ant[i]<=N)
soldat[i]=ant[i];
i=ant[i];
}
}
return F;
}
int main()
{
int i,j,k,auxx;
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];
x[k]=i;
y[k]=j+N;
}
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;
auxx=x[j/2];
x[j/2]=x[j];
x[j]=auxx;
auxx=y[j/2];
y[j/2]=y[j];
y[j]=auxx;
j/=2;
}
}
i=N*N;
while(i>1)
{
aux=dist[1];
dist[1]=dist[i];
dist[i]=aux;
auxx=x[1];
x[1]=x[i];
x[i]=auxx;
auxx=y[1];
y[1]=y[i];
y[i]=auxx;
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;
auxx=x[k];
x[k]=x[j];
x[j]=auxx;
auxx=y[k];
y[k]=y[j];
y[j]=auxx;
j=k;
}
}
int li,lf,mij,ind;
double distMin,totalMin;
/*
for(i=1;i<=N*N;i++)
{
if(viz[x[i]]==0)
{
viz[x[i]]=1;
nv++;
}
if(viz[y[i]]==0)
{
viz[y[i]]=1;
nv++;
}
if(nv==2*N) break;
}
*/
li=1;
lf=N*N;
while(li<=lf)
{
mij=(li+lf)>>1;
if( simple_flow(mij) == N )
{
ind=mij;
lf=mij-1;
}
else
li=mij+1;
}
fprintf(fout,"%f %f\n",dist[ind],dist[ind]);
fin.close();
fclose(fout);
return 0;
}