oilpipeline.txt

这是一个关于输油管道的算法,很是经典,不信,可以看一下.

#include<stdio.h>
#include<string.h>
#define MaxL 100
#define MaxN 10000
#define MaxNum(a,b) (a>b?a:b)
#define MinNum(a,b) (a<b?a:b)

int map[MaxL][MaxL];
int n,wx[MaxN],wy[MaxN];
int pipe;
int sy[MaxL],ty[MaxL];

int init()
{memset(map,0,sizeof(map));
 n=0;
 do
  {scanf("%d %d",&wx[n],&wy[n]);
   if (wx[n]==0&&wy[0]==0) return 0;
   if (wx[n]==-1&&wy[n]==-1) return 1;
   n++;
  }
 while (1);
}

int pipel(int p)
{ int tmp=0,i;
 for (i=0; i<MaxL; i++)
  tmp+=(MaxNum(ty[i],p)-MinNum(sy[i],p));
 return tmp;
}

void search()
{ int i,j,min_tol,tmp;
 for (i=0; i<MaxL; i++)
  {sy[i]=MaxL; ty[i]=0;}
 for (i=0; i<n; i++)
  {sy[wx[i]]=MinNum(sy[wx[i]],wy[i]);
   ty[wx[i]]=MaxNum(ty[wx[i]],wy[i]);
  }
 min_tol=pipel(1); pipe=1;
 for (i=2; i<MaxL; i++)
  {tmp=pipel(i);
   if (tmp<min_tol) {min_tol=tmp; pipe=i;}
  }
 for (i=0; i<MaxL; i++) map[pipe][i]=1;
 for (i=0; i<MaxL; i++)
  if (sy[i]<=ty[i])
   for (j=MinNum(sy[i],pipe); j<=MaxNum(ty[i],pipe); j++)
    map[j][i]=1;
 for (i=0; i<n; i++) map[wy[i]][wx[i]]=2;
}

void show()
{ int i,j,minx=MaxL,miny=MaxL,maxx=0,maxy=0;
  char typ[5];
  char typ2[4]={"  "};
 typ[4]=0; typ[3]='+'; typ[2]='d'; typ[0]='%';
 for (i=0; i<n; i++)
  {minx=MinNum(wx[i],minx);
   miny=MinNum(wy[i],miny);
   maxx=MaxNum(wx[i],maxx);
   maxy=MaxNum(wy[i],maxy);
  }
 if (minx%5==0) minx-=5; else minx-=(minx%5);
 if (miny%5==0) miny-=5; else miny-=(miny%5);
 maxx+=(5-(maxx%5));
 maxy+=(5-(maxy%5));
 if (maxx-minx>70||maxy-miny>20)
  {printf("Map is too big to draw for pipeline at %d\n",pipe); return;}
 if (maxy<10) {typ[1]='1'; typ2[1]=0;} else {typ[1]='2'; typ2[2]=0;}
 for (printf(typ,maxy),i=minx+1; i<=maxx; i++)
  if (i%5==0) printf("----+");
 printf("\n");
 for (i=maxy-1; i>miny; i--)
  {if (i%5==0) printf(typ,i); else {printf(typ2); printf("|");}
   for (j=minx+1; j<maxx; j++)
    if (map[i][j]==0) printf(".");
    else if (map[i][j]==1) printf("*");
    else if (map[i][j]==2) printf("@");
   if (i%5==0) printf("+\n"); else printf("|\n");
  }
 for (printf(typ,miny),i=minx+1; i<=maxx; i++)
  if (i%5==0) printf("----+");
 printf("\n");
 for (printf(typ2),i=minx; i<maxx; i++)
  if (i%5==0) printf("%-5d",i);
 printf("%d\n",maxx);
}

int main()
{ int testdata=0;
 while (init())
  {printf("OIL FIELD %d\n",++testdata);
   search();
   show();
  }
 return 0;
}