CodingTrip

携程全球数据中心建设

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 725 Accepted Submission(s): 307

Problem Description

携程为了扩展全球在线旅游业务，决定在全球建设多数据中心，以便提高网站的访问速度和容灾处理。
为了实现每个数据中心的数据能互通，数据中心之间需要通过光纤连接。为了节约光纤成本，我们计划采用点对点方式来达到最终各个数据中心的数据互通，每个数据中心本身都可以作为数据中转站。做为全球多数据中心设计者，您需要知道最短的光纤总长度，来把所有的数据中心都实现互通。假设地球是个圆球，且表面是平滑的，并且没有任何阻碍物（河流，山脉）。

输入数据是一组数据中心的经纬度
纬度: -90° 到 +90°
经度: -180° 到 +180°
(圆周率pi= 3.14159265358979323846)

Input

第一行第一个整数N(1≤N≤100)，表示有多少个用例. 每个用例包含了:
第一行，小数D(1≤D≤1,000,000)，表面圆球的直径(公里).
第二行，小数L(1≤L≤1,000,000) 光纤总长度 (公里).
第三行，整数C(1≤C≤100) ，表示数据中心的数量.
接下来的C行, 每行有2个形如"X Y"的小数，表示每个数据中心的纬度(-90≤X≤90)和经度 (-180≤Y≤180).

Output

每个用例输出一行. 如果光纤长度L足够连接所有数据中心，输出"Y", 否则输出"N"。

Sample Input

2 12742 5900 3 51.3 0 42.5 -75 48.8 3 12742 620 2 30.266 97.75 30.45 91.1333

Sample Output

Y N

题目的意思就是给你球上的若干个点，让你求这些点构成的最小生成树的长度如果比L大输出“N"，否则输出”Y"。在网上找了一个求球上两点距离的模板，求出距离之后直接kruskal就过了。

代码如下：

  1 /*
  2 ID: asif
  3 LANG: C++
  4 TASK: test
  5 */
  6 //# pragma comment(linker, "/STACK:102400000,102400000")
  7 # include<iostream>
  8 # include<cstdio>
  9 # include<cstdlib>
 10 # include<cstring>
 11 # include<algorithm>
 12 # include<cctype>
 13 # include<cmath>
 14 # include<string>
 15 # include<set>
 16 # include<map>
 17 # include<stack>
 18 # include<queue>
 19 # include<vector>
 20 # include<numeric>
 21 using namespace std;
 22 const int maxn=111;
 23 const double inf=0.000001;
 24 const int INF=~0U>>1;
 25 const int mod=1000000007;
 26 # define PI (acos(0)*2.0)
 27 # define lson l,m,rt<<1
 28 # define rson m+1,r,rt<<1 | 1
 29 # define PS printf("
")
 30 # define S(n) scanf("%d",&n)
 31 # define P(n) printf("%d
",n)
 32 # define Ps(n) printf(" %d",(n))
 33 # define SB(n) scanf("%lld",&n)
 34 # define PB(n) printf("%lld
",n)
 35 # define PBs(n) printf(" %lld",n)
 36 # define SD(n) scanf("%lf",&n)
 37 # define PD(n) printf("%.3lf
",n)
 38 # define Sstr(s) scanf("%s",s)
 39 # define Pstr(s) printf("%s
",s)
 40 # define S0(a) memset(a,0,sizeof(a))
 41 # define S1(a) memset(a,-1,sizeof(a))
 42 # define pi 3.14159265358979323846
 43 typedef long long ll;
 44 int n,f[maxn],m;
 45 struct node
 46 {
 47     int x;
 48     int y;
 49     double v;
 50 };
 51 node edge[maxn*maxn];
 52 int equal(double x,double y)
 53 {
 54     if(x-y>=-inf&&x-y<=inf)
 55         return 0;
 56     else if(x-y>inf)
 57         return 1;
 58     return -1;
 59 }
 60 double rad(double d)
 61 {
 62     return d * pi / 180.0;
 63 }
 64 double getDistance(double longitude1, double latitude1,
 65         double longitude2, double latitude2,double EARTH_RADIUS)       //网上找的求球上两点距离的函数模板
 66         {
 67     double Lat1 = rad(latitude1);
 68     double Lat2 = rad(latitude2);
 69     double a = Lat1 - Lat2;
 70     double b = rad(longitude1) - rad(longitude2);
 71     double s = 2 * asin(sqrt(pow(sin(a / 2), 2)
 72             + cos(Lat1) * cos(Lat2)
 73             * pow(sin(b / 2), 2)));
 74     s = s * EARTH_RADIUS;
 75     return s;
 76 }
 77 void init()
 78 {
 79     for(int i=0;i<=n;i++)
 80         f[i]=i;
 81 }
 82 bool cmp(node t1,node t2)
 83 {
 84     return t1.v<t2.v;
 85 }
 86 int find(int x)
 87 {
 88     if(x==f[x])
 89         return x;
 90     return find(f[x]);
 91 }
 92 void unin(int x,int y)
 93 {
 94     x=find(x);
 95     y=find(y);
 96     if(x!=y)
 97         f[x]=y;
 98 }
 99 double kruskal()    //kruskal算法求最小生成树
100 {
101     int num=0;
102     double sum=0;
103     for(int i=0;i<m;i++)
104     {
105         int u=edge[i].x,v=edge[i].y;
106         double w=edge[i].v;
107         if(find(u)!=find(v))
108         {
109             num++;
110             sum+=w;
111             unin(u,v);
112         }
113         if(num>=n-1)
114             break;
115     }
116     return sum;
117 }
118 int main()
119 {
120     //freopen("input.in", "r", stdin);
121     //freopen("output.out", "w", stdout);
122     int T;
123     S(T);
124     while(T--)
125     {
126         double D,L,x[111],y[111];
127         scanf("%lf%lf%d",&D,&L,&n);
128         m=0;
129         init();
130         for(int i=0;i<n;i++)
131             scanf("%lf%lf",&x[i],&y[i]);
132         for(int i=0;i<n-1;i++)
133         {
134             for(int j=i+1;j<n;j++)
135             {
136                     edge[m].v=getDistance(y[i],x[i],y[j],x[j],D/2);
137                     edge[m].x=i;
138                     edge[m].y=j;
139                     m++;
140             }
141         }
142         sort(edge,edge+m,cmp);
143         double ans=kruskal();
144         //PD(ans);
145         if(ans<=L)
146             puts("Y");
147         else
148             puts("N");
149     }
150     return 0;
151 }

View Code