携程编程赛第一场C题（球面最小生成树）

题意：球面上给出n个点的经纬度，求最小生成树总路径长度是否小于给定的一个长度；

解法：球面上的最小生成树，关键是有两点的经纬度得到两点的球面距离：

          球面距离公式：length=R*acos(cosβ1*cosβ2*cos(α1-α2)+sinβ1*sinβ2),β1,β2分别为纬度，α1，α2分别为经度；

代码：

/****************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>

using namespace std;

#define eps 1e-8
double pi=acos(-1);
typedef long long LL;
int parent[110];
int getparent(int k)
{
    if(parent[k]==k)
        return k;
    return parent[k]=getparent(parent[k]);
}
struct p
{
    double x,y;
} ps[110];
struct point
{
    int a,b;
    double length;
} points[100100];
int p=0;
bool operator<(point a,point b)
{
    return a.length<b.length;
}


double R,L;
int C;
bool OK(int a,int b)
{
    int ta=getparent(a);
    int tb=getparent(b);
    if(ta==tb)
        return false;
    parent[ta]=tb;
    return true;
}

int main()
{
 int t;cin>>t;
 while(t--)
 {
     scanf("%lf%lf%d",&R,&L,&C);R/=2;
     p=0;
     for(int i=0;i<C;i++)
     {
         scanf("%lf%lf",&ps[i].x,&ps[i].y);
         parent[i]=i;
     }
     for(int i=0;i<C;i++)
        for(int j=i+1;j<C;j++)
     {
         double x1=ps[i].x/180*pi;
         double x2=ps[j].x/180*pi;
         double y1=ps[i].y/180*pi;
         double y2=ps[j].y/180*pi;
         points[p].a=i,points[p].b=j;
         double tool=abs(y1-y2);
         if(tool>pi)
            tool-=pi;
         points[p++].length=R*acos(cos(x1)*cos(x2)*cos(tool)+sin(x1)*sin(x2));
     }
     sort(points,points+p);
     double sum=0;
     for(int i=0;i<p;i++)
     {
         if(OK(points[i].a,points[i].b))
            sum+=points[i].length;
     }
     if(sum<=L)
        cout<<"Y\n";
     else
        cout<<"N\n";
 }
   return 0;
}
/*
R*arccos(cosx1*cosx2*cos(y1-y2)+sinx1*sinx2);
                     */

携程编程赛第一场C题（球面最小生成树）,布布扣,bubuko.com

携程编程赛第一场C题（球面最小生成树）

原文：http://blog.csdn.net/xiefubao/article/details/23395823