解題區/解題區 - UVa

UVa 10184 - Equidistance

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

在地球上，給定許多地點的經緯度，兩個人必須在中立領域中見面，兩個人分別在球面上的兩個點，中立領域則是兩點連線的中點，垂直拉出的一個大圓 (球體上的一圈)。

它們現在位於地球上某點，請問到大圓的最短距離為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Ulm             48.700 10.500
Freiburg        47.700 9.500
Philadelphia    39.883 -75.250
SanJose         37.366 -121.933
Atlanta         33     -84
Eindhoven       52     6
Orlando         28     -82
Vancouver       49     -123
Honolulu        22     -157
NorthPole       90     0
SouthPole       -90    0
#
Ulm Freiburg Philadelphia
SanJose Atlanta Eindhoven
Orlando Vancouver Honolulu
NorthPole SouthPole NorthPole
Ulm SanDiego Orlando
NorthPole SouthPole SouthPole
Ulm Honolulu SouthPole
#

Sample Output

1
2
3
4
5
6
7
Philadelphia is 690 km off Ulm/Freiburg equidistance.
Eindhoven is 3117 km off SanJose/Atlanta equidistance.
Honolulu is 4251 km off Orlando/Vancouver equidistance.
NorthPole is 10019 km off NorthPole/SouthPole equidistance.
Orlando is ? km off Ulm/SanDiego equidistance.
SouthPole is 10019 km off NorthPole/SouthPole equidistance.
SouthPole is 1494 km off Ulm/Honolulu equidistance.

Solution

特別小心，詢問的兩點相同，導致整個球體都是中立領域。

對於球體找到圓的最短距離，找出夾角即可。

首先拉出 AB 線，將其移動至眼前水平放置 (O A B 同一水平面)，又 OM 會於 AB 中點拉出來的大圓夾角 theta (直接 AB 和 OM 內積得角度)，此時的大圓應該是垂直 90 度，藉此得到最短距離。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <map>
using namespace std;
struct Point {
    double x, y, z;
    Point(double a=0, double b=0, double c=0):
        x(a), y(b), z(c) {}
    Point operator-(const Point &a) const {
        return Point(x - a.x, y - a.y, z - a.z);
    }
    double len() {
        return sqrt(x * x + y * y + z * z);
    }
};
int main() {
    const double pi = acos(-1);
    const double earth_r = 6378;
    char s[1024], s2[1024], s3[1024];
    double lat, lon; //  latitude, longitude
    map<string, Point> R;
    while (scanf("%s", s) == 1) {
        if (!strcmp(s, "#"))
            break;
        scanf("%lf %lf", &lat, &lon);
        lat = lat * pi / 180.0;
        lon = lon * pi / 180.0;
        double x, y, z;
        x = earth_r * cos(lat) * cos(lon);
        y = earth_r * cos(lat) * sin(lon);
        z = earth_r * sin(lat);
        R[s] = Point(x, y, z);
    }
    while (scanf("%s", s) == 1) {
        if (!strcmp(s, "#"))
            break;
        scanf("%s %s", s2, s3);
        if (R.find(s) == R.end() || R.find(s2) == R.end() || R.find(s3) == R.end()) {
            printf("%s is ? km off %s/%s equidistance.\n", s3, s, s2);
        } else {
            Point A = R[s], B = R[s2], M = R[s3];
            Point AB = A - B, OM = M;
            double dot = AB.x * OM.x + AB.y * OM.y + AB.z * OM.z;
            double theta = acos(fabs(dot) / AB.len() / OM.len());
            double ret = (pi /2 - theta) * earth_r;
#define eps 1e-6
            if (fabs(AB.x) < eps && fabs(AB.y) < eps && fabs(AB.z) < eps)
                ret = 0;
            printf("%s is %.0lf km off %s/%s equidistance.\n", s3, ret, s, s2);
        }
    }
    return 0;
}