島嶼渡假↘下殺$4900起直擊★美車模手癢不小心...輕忽小中風,當心變殘障老伯送飲料 遭學生糾察...
2013-05-11 13:38:21 人氣(23) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][3D球面距離] 10316 - Airline Hub

0
收藏
0
推薦

Problem E

Airline Hub

Input: standard input

Output: standard output

Time Limit: 2 seconds

Memory Limit: 32 MB

 

World Wide Flyer (WWF) 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

Input file contains several sets of input. Each set 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. The input floating point numbers will not have more than two digits after the decimal point. Input is terminated by end of file.

 

Output

For each set of input print the latitude and longitude of the airport that best serves as a hub in a single line. If there is more than one airport that best serves as a hub print the one that appears last in the input of the corresponding input set. Your output should always contain two digits after the decimal point.

 

Sample Input

3
3.2 -15.0
20.1 -175
-30.2 10
3
3.2 -15.0
20.1 -175
-30.2 10

 

Sample Output

3.20 -15.00
3.20 -15.00

(The Decider Contest, Source: Waterloo ACM Programming Contest)

這種題目,將其座標化(x, y, z),得 OAB 三角形,算圓心角 theta。
接著在計算弧長 R*theta

#include <stdio.h>
#include <math.h>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
const double R = 6378;
const double pi = acos(-1);
#define eps 1e-6
int main() {
    int n;
    int i, j, k;
    double w, theta;
    double x[1005], y[1005], z[1005];
    double W[1005], THETA[1005];
    int cases = 0;
    while(scanf("%d", &n) == 1) {
        for(i = 0; i < n; i++) {
            scanf("%lf %lf", &W[i], &THETA[i]);
            w = W[i]*pi/180.0, theta = THETA[i]*pi/180.0;
            x[i] = R*cos(w)*sin(theta);
            y[i] = R*cos(w)*cos(theta);
            z[i] = R*sin(w);
        }
        double mx, mn = 1e+30;
        double rx = W[0], ry = THETA[0];
        for(i = 0; i < n; i++) {
            mx = 0;
            for(j = 0; j < n; j++) {
                if(i == j)
                    continue;
                double AB = sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2)+pow(z[i]-z[j],2));
                double OA = R, OB = R;
                theta = acos((OA*OA+OB*OB-AB*AB)/(2*OA*OB));
                mx = max(mx, R*theta);
                if(mx > mn+eps) break;
            }
            if(mn >= mx-eps) {
                mn = mx;
                rx = W[i];
                ry = THETA[i];
            }
        }
        printf("%.2lf %.2lf\n", rx, ry);
    }
    return 0;
}

10316Airline Hub球面距離
台長:Morris
人氣(23) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][ad-hoc] 11319 - Stupid Sequence
此分類上一篇:[UVA][組合、排容] 12572 - RMQ Overkill

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文