AOJ1107 Spiral Footrace

問題リンク Spiral Footrace

• 概要

座標(0, 0)に北を向いて立っている。N個の点が与えられる。N個の点を順番に辿り、最後の点についた時の総距離を答えよ。
点を辿る順番は、向いている方向とその点のある方向との角度が一番小さいものとする。
1 <= N <= 40
0 <= x, y <= 500

• 解法

幾何＋シミュレーション問題です。
向いている方向のベクトルをY、現在地からある点へのベクトルをXとしたとき、これらの間の角度θ(ラジアン)は
θ = atan2(X×Y, X・Y)
で求められます。
このθを各点について求め、一番小さかった点を次の点とします。
θはacos(|X||Y|/X×Y)でも求まりますが、精度が悪く、正しい答えを出すことができませんでした。atan2を使った方がいいです。

• ソース

import java.util.Scanner;

//Spiral Footrace
public class AOJ1107 {

	class P{
		int x, y;
		public P(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	
	void run(){
		double EPS = 1e-6;
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			P[] p = new P[n];
			for(int i=0;i<n;i++)p[i]=new P(sc.nextInt(), sc.nextInt());
			boolean[] u = new boolean[n];
			P t = new P(0, 0);
			P h = new P(0, 1);
			P pre = new P(0, 0);
			double res = 0;
			for(int i=0;i<n;i++){
				int id = -1;
				double min = 360;
				double d = 1<<29;
				for(int j=0;j<n;j++){
					if(u[j])continue;
					double dist = Math.hypot(p[j].x-pre.x, p[j].y-pre.y);
					double x1 = p[j].x-pre.x;
					double y1 = p[j].y-pre.y;
					double x2 = h.x-t.x;
					double y2 = h.y-t.y;
					double thita = Math.atan2(x1*y2-x2*y1, x1*x2+y1*y2);
					if(thita+EPS<min){
						id = j;
						min = thita;
						d = dist;
					}
					else if(Math.abs(thita-min)<EPS&&dist<d){
						id = j;
						d = dist;
					}
				}
				u[id] = true;
				res += d;
				pre = p[id];
				if(i==0){
					h = p[id];
				}
				else{
					t = h;
					h = p[id];
				}
			}
			System.out.printf("%.1f\n", res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1107().run();
	}
}