学步园

#include <stdio.h>
#include <cmath>
#include <cstring>
#define maxn 101
#define r 16.7/2.0
#define pie acos(-1.0)
struct point
{
    double x,y;
}p[maxn];
double dis(double x1,double y1,double x2,double y2,double R)
{    //参数都是弧度表示的
     x1=pie*x1/180.0;
     y1=pie*y1/180.0;
     x2=pie*x2/180.0;
     y2=pie*y2/180.0;
     return R*(acos(cos(x1)*cos(x2)*cos(y1-y2)+sin(x1)*sin(x2)));
}
double dist[maxn];
double map[maxn][maxn];
bool vis[maxn];
int main()
{
    int n;
    int ca=1;
    while(scanf("%d",&n)==1&&n)
    {
        for(int i=1;i<=n;i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        map[i][j]=map[j][i]=dis(p[i].y,p[i].x,p[j].y,p[j].x,r);
        memset(vis,false,sizeof(vis));
        memset(dist,0x7f,sizeof(dist));
        dist[1]=0;
        double sum=0;
        for(int i=1;i<=n;i++)
        {
            double min=0x7f;
            int k=0;
            for(int j=1;j<=n;j++)
            {
                if(!vis[j]&&dist[j]<min)
                {
                    min=dist[j];
                    k=j;
                }
            }
            vis[k]=true;
            sum+=min;
            for(int j=1;j<=n;j++)
            {
                if(map[k][j]<dist[j])
                dist[j]=map[k][j];
            }
        }
        printf("Case %d: %.2lf miles\n",ca++,sum);
    }
    return 0;
}