POJ-2587: Airline Hub

keyword

空間幾何　球座標　C

問題概要

球面上に点がN(<1000)個あり、緯度と経度が与えられる。各点への距離(球面上)の最大値が最小になる点を答える問題。

解法

全探索で間に合う。球面上での距離の求め方は、内積とacos使ってなす角を求めてやればよい。

感想

度数法と弧度法間違えるという典型的な間違いにずっと気がつかなかった。

#include <stdio.h>
#include <math.h>

#define MAX_N 1009

int N;
const double PI = atan(1.0)*4;
double xs[MAX_N], ys[MAX_N], zs[MAX_N];
double theta[MAX_N], phi[MAX_N];

double sq(double x){ return x*x; }

void init(){
	int i;
	double th, ph;
	for(i=0; i<N; i++){
		th = theta[i]*PI/180; ph = phi[i]*PI/180;
		xs[i] = cos(th)*cos(ph);
		ys[i] = sin(th)*cos(ph);
		zs[i] = sin(ph);
	}
}

void solve(){
	int i,j,key=0;
	double minDist = 1e10, maxDist, tmp, alpha;
	init();
	for(i=0; i<N; i++){
		maxDist = 0;
		for(j=0; j<N; j++)if(i!=j){
			alpha = (xs[i]*xs[j]+ys[i]*ys[j]+zs[i]*zs[j])/
					(sqrt(sq(xs[i])+sq(ys[i])+sq(zs[i]))*sqrt(sq(xs[j])+sq(ys[j])+sq(zs[j])));
			tmp = acos(alpha);
			if(tmp > maxDist){
				maxDist = tmp;
			}
		}
		if(minDist > maxDist){
			minDist = maxDist;
			key = i;
		}
	}
	printf("%.2f %.2f\n",phi[key], theta[key]);
}

int main(){
	int i;
	for(i=0,scanf("%d ",&N);i<N;i++){
		scanf("%lf%lf ",phi+i,theta+i);
	}
	solve();
	return 0;
}