UVA 11817：球面幾何計算大圓弧長與弦長差

問題描述

給定兩點經緯度，地球半徑 R=6371009。求大圓弧長與弦長的差值（四捨五入整數）。

經緯度轉三維坐標

Point3 get_coord(double R, double lat, double lng) {
    lat = lat/180*PI; lng = lng/180*PI;
    return Point3(R*cos(lat)*cos(lng), R*cos(lat)*sin(lng), R*sin(lat));
}

計算流程

1. 兩點轉三維向量 p1, p2。
2. 弦長 d = |p1-p2|。
3. 圓心角 θ = 2*asin(d/(2R))。
4. 弧長 s = R*θ。
5. 答案 round(s - d)。

代碼實現

#include 
#include 
const double PI = acos(-1.0), R = 6371009;
struct Point3 { double x,y,z; };
double torad(double d) { return d/180*PI; }
Point3 get_coord(double lat, double lng) {
    lat = torad(lat); lng = torad(lng);
    return {R*cos(lat)*cos(lng), R*cos(lat)*sin(lng), R*sin(lat)};
}
double dist(Point3 a, Point3 b) {
    double dx=a.x-b.x, dy=a.y-b.y, dz=a.z-b.z;
    return sqrt(dx*dx+dy*dy+dz*dz);
}
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        double lat1, lng1, lat2, lng2;
        scanf("%lf%lf%lf%lf", &lat1, &lng1, &lat2, &lng2);
        Point3 p1 = get_coord(lat1, lng1);
        Point3 p2 = get_coord(lat2, lng2);
        double d = dist(p1, p2);
        double arc = 2*asin(d/(2*R))*R;
        printf("%.0f\n", arc - d);
    }
}

精度注意

• 用 double 足夠，asin 參數域 [-1,1] 需 clamp。
• 輸出四捨五入整數 %.0f。