第二十二题:

题目描述：

2587:Airline Hub

题目链接：

P2587——Airline Hub——柒行（www.oj7.cn）

题目来源：

Waterloo local 2000.01.29

总时间限制:

1000ms

内存限制:

65536kB

World Wide Flyer has landing rights at several airports throughout the world. They wish to place their central hub at the airport that minimizes the maximum direct flying distance from the hub to any other airport in the world.

输入

Input consists of a line containing n <= 1000, the number of airports. n lines follow, each giving the latitude (between -90 and +90 degrees) and longitude (between -180 and +180 degrees) of an airport.

输出

To two decimal places, give the latitude and longitude of the airport that best serves as a hub. If there are several any one will do.

样例输入

3
3.2 -15.0
20.1 -175
-30.2 10

样例输出

3.20 -15.00

中文题面：

环球飞行者航空公司在全球多个机场拥有降落权。他们希望将其中心枢纽设在一个机场，该机场能最小化从枢纽到世界上任何其他机场的最大直接飞行距离。

输入：

第一行包含一个整数$n$ $（n <= 1000）$，表示机场的数量。接下来的$n$行，每行给出一个机场的纬度 （范围在$-90$到$+90$度之间） 和经度 （范围在$-180$到$+180$度之间）。

输出：

以小数点后两位的形式给出最适合作为枢纽的机场的纬度和经度。如果有多个这样的机场，任何一个都可以。

样例输入

3
3.2 -15.0
20.1 -175
-30.2 10

样例输出

3.20 -15.00

算法标签：

几何距离计算 贪心算法

解题思路：

使用$Haversine$公式来计算球面上两点之间的最短距离。对于每个机场，计算它到所有其他机场的距离，选择最大距离最小的那个机场作为中心枢纽。输出该机场的纬度和经度，保留两位小数。

实现步骤：

1.读取输入数据，包括机场数量和每个机场的经纬度。 2.使用$Haversine$公式计算任意两个机场之间的距离。 3.对每个机场，计算其到所有其他机场的最大距离，并记录下这些最大距离。 4.在所有机场的最大距离中找到最小值，对应的机场即为最佳中心枢纽。 5.输出该机场的纬度和经度，格式化为两位小数。

C++实现：

#include <iostream>
#include <math.h>
#include <stdio.h>
#define PI 3.14159265358979323846
#define R 6371
using namespace std;
double a(double degree){
    return degree*(PI/180);
}
double b(double lat1, double lon1, double lat2, double lon2){
    double dLat=a(lat2-lat1);
    double dLon=a(lon2-lon1);
    lat1=a(lat1);
    lat2=a(lat2);
    double e=sin(dLat/2)*sin(dLat/2)+
               sin(dLon/2)*sin(dLon/2)*cos(lat1)*cos(lat2);
    double f=2*atan2(sqrt(e),sqrt(1-e));
    return R*f;
}
int main(){
    int n;
    cin>>n;
    double c[n],d[n];
    for(int i=0; i<n; i++){
    	cin>>c[i]>>d[i];
    }
    double minMaxDist=1e9;
    int bestIndex=0;
    for(int i=0; i<n; i++){
        double maxDist=0;
        for(int j=0; j<n; j++){
            if(i!=j){
                double dist=b(c[i],d[i],c[j],d[j]);
                if(dist>maxDist){
                    maxDist=dist;
                }
            }
        }
        if(maxDist<minMaxDist){
            minMaxDist=maxDist;
            bestIndex=i;
        }
    }
    printf("%.2f %.2f\n",c[bestIndex],d[bestIndex]);
    return 0;
}