Airline Hub

参考:http://blog.csdn.net/mobius_strip/article/details/12731459

#include <stdio.h>
#include <cmath>
#include <iostream>

struct Point
{
    double lat, lon;
};

double dist(double lat1, double lon1, double lat2, double lon2)
{
    double p = acos(-1.0);
    lat1 *= p / 180.0; lon1 *= p / 180.0;
    lat2 *= p / 180.0; lon2 *= p / 180.0;
    return cos(lat1)*cos(lat2)*cos(lon1 - lon2) + sin(lat1)*sin(lat2);
}

int main()
{
    const int count = 1001;
    static Point pts[count];
    static double dis[count][count];
    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i)
    {
        std::cin >> pts[i].lat >> pts[i].lon;
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            dis[i][j] = dis[j][i] = dist(pts[i].lat, pts[i].lon, pts[j].lat, pts[j].lon);
        }
    }
    double min = dis[0][1];
    int hub = 0;
    for (int i = 0; i < n; ++i)
    {
        double max = 0.0;
        for (int j = 0; j < n; ++j)
        {
            if (max < dis[i][j])
            {
                max = dis[i][j];
            }
        }
        if (min > max)
        {
            min = max;
            hub = i;
        }
    }
    printf("%0.2f %0.2f
",pts[hub].lat,pts[hub].lon);
    return 0;
}