ball.cpp

每对节点间最短路径 Floyd-Warshall 算法 D[i,j]表示从i到j的最短距离； P[i,j]表示从i到j的最短路径上j 的父节点

/******************************************
*                                         *
*     example of using prim algorithm     *
*                                         *
*                   copyright starfish    *
*                        2000/10/24       *
*                                         *
*******************************************/
#include <stdio.h>
#include <iostream.h>
#include <assert.h>
#include <math.h>
#include <stdlib.h>


#define input "ball.in"      //Input file name
#define output "ball.out"    //Output file name

#define max_point 5        //max point count

#define infinity 1000000      // a big int
#define max_N max_point+2   // the max count of vertexes

typedef double Graph[max_N][max_N];   //use adjacent matrix to represent graph

FILE *fin,*fout;
int probN=0;
int n,h,x[max_point],y[max_point];


int read_case()
{
   int i;
   if (feof(fin)) return 0;
   fscanf(fin,"%d %d\n",&n,&h); //n is the count of points and h is the height of the chunnel
   if (n==0) return 0;         // n=0 indicate the end of test case
   probN++;
   for (i=0;i<n;i++) fscanf(fin,"%d %d\n",&x[i],&y[i]); // next n line is the coordinate of n points
   return 1;
}

//using prim algorithm to cal minimal span tree, but something is modified

void prim(Graph G,int vcount,int father[],int root)
{
   int i,j,k;
   double lowcost[max_N];
   int used[max_N],closeset[max_N];

   for (i=0;i<vcount;i++)
      {
         lowcost[i]=G[root][i];
         closeset[i]=root;    //notice: here vertex 1 is G[0]
         used[i]=0;        //mark all vertexes have not been used
         father[i]=-1;      // that means no father
         }
   used[root]=1;              // mark vertex 1 has been used
   for (i=1;i<vcount;i++)
      {
         j=0;
         while (used[j]) j++;
         for (k=0;k<vcount;k++)
            if ((!used[k])&&(lowcost[k]<lowcost[j])) j=k;  //find the next tree edge
         father[j]=closeset[j];   //record the tree edge using father array
         used[j]=1;               //mark vertex j+1 has been used
         for (k=0;k<vcount;k++)
            if (!used[k]&&(G[j][k]<lowcost[k]))  //modify the lowcost
               {
                  lowcost[k]=G[j][k];
                  closeset[k]=j;
                  }
         }

   }


double distance(int x1,int y1,int x2,int y2)
{
  return(sqrt(double((x1-x2)*(x1-x2))+double((y1-y2)*(y1-y2))));
   }


void solve_case()
{
   int i,j,k;
   Graph G;
   int father[max_N];
   double result;

   for (i=0;i<n;i++)                //constructure the graph
      for (j=i;j<n;j++)
         G[i][j]=G[j][i]=distance(x[i],y[i],x[j],y[j]);

   for (i=0;i<n;i++)             //add two vertexes represent the top and bottom wall
      {
         G[i][n]=G[n][i]=y[i];
         G[i][n+1]=G[n+1][i]=h-y[i];
         }
  G[n][n+1]=G[n+1][n]=h;
  prim(G,n+2,father,n+1);
//  for (i=0;i<n+1;i++) fprintf(fout,"%d ",father[i]);
//  fprintf(fout,"\n");

 //find the max significance (the distance between two points or between point and wall) of the
 //way in the minimal sapn tree from vertex n+1 to vertex n,ie. from top wall to bottom wall.
  i=n;
  result=G[father[i]][i];
  while (father[i]!=n+1)
     {
        i=father[i];
        result=max(result,G[father[i]][i]);
        }
  fprintf(fout,"Case %d\n",probN);
  fprintf(fout,"%8.3f\n\n",result/2); //print the max radius of the ball which can go through the chunnel

}


int main()
{
   assert(fin=fopen(input,"r"));
   assert(fout=fopen(output,"w"));   //if there is no output file, comment this line
   while (read_case()) solve_case();
   fclose(fin);
   fclose(fout);                    //if there is no output file, comment this line
	return 0;
}