AOJ0204 UFO Shooting Down Operation

AOJ Volume2

問題リンク UFO Shooting Down Operation

  • 解法

幾何+シミュレーション問題です。
まず、準備立てとして次のものを求めておきます。
1. ufoの位置(x, y)
2. 1分毎のufoの移動量ベクトル
3. 原点からの距離
自分のソースの場合、1はufo[i][0]とufo[i][1]にそれぞれx,yが、2はadv[i][0], adv[i][1]に入っています。移動量ベクトルはUFOの初期位置ベクトルを逆にし正規化する(ベクトルの大きさでx成分、y成分を割る)ことで求めます。3は初期位置の距離から毎分UFOの分速を引くことで簡単に求められます。
シミュレーション部分の説明をします。
まず、Rより大きい距離離れているUFOの中で最も近い位置にいるUFOを見つけます。このとき、R以下の距離に入っているUFOはレーザーの当たらない範囲内に逃げおおせたことになるので、カウントし、そのUFOに今後考慮しない印をつけておきます。また、Rより離れているUFOがいない場合はシミュレーション終了です。
レーザーを射出するUFOが決まったら、レーザーの方向ベクトルPが定まります。(ufo[i][0], ufo[i][1])というベクトルがレーザーの方向ベクトルです。これは正規化しておきます。
さて、射出する方向にいるUFOは撃墜できると分かりますが、このレーザーによって別のUFOも撃墜できるかチェックしないといけません。チェックしたいUFOをiとします。まず、UFO i の中心の位置ベクトルをCとし、半径をrとします。このとき、PとCとrを使って以下の図のようなtの2次方程式が導けます。

このtは、レーザーとUFOが衝突する場所t1, t2を求める式となります。つまり、このt1、t2のうち、いずれかがRより大きければ、レーザーの効かない範囲外でレーザーを当てることができることになり、UFO i を撃墜することができます。

  • ソース
import java.util.Scanner;

//UFO Shooting Down Operation
public class AOJ0204 {

	double dot(double[] a, double[] b){
		return a[0]*b[0]+a[1]*b[1];
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		while(true){
			int R = sc.nextInt();
			int n = sc.nextInt();
			if((R|n)==0)break;
			double[][] ufo = new double[n][4];
			for(int i=0;i<n;i++)for(int j=0;j<4;j++)ufo[i][j]=sc.nextDouble();
			double[][] adv = new double[n][2];
			double[] dist = new double[n];
			for(int i=0;i<n;i++){
				double norm = Math.hypot(ufo[i][0], ufo[i][1]);
				dist[i] = norm-ufo[i][3];
				adv[i][0] = -ufo[i][0]/norm*ufo[i][3];
				adv[i][1] = -ufo[i][1]/norm*ufo[i][3];
				ufo[i][0] += adv[i][0];
				ufo[i][1] += adv[i][1];
			}
			boolean[] u = new boolean[n];
			int c = 0;
			while(true){
				double min = 1<<20;
				int id = -1;
				for(int i=0;i<n;i++){
					if(u[i])continue;
					double d = dist[i];
					if(d<=R){
						u[i] = true;
						c++;
					}
					else if(d<min){
						min = d;
						id = i;
					}
				}
				if(id==-1)break;
				double norm = Math.hypot(ufo[id][0], ufo[id][1]);
				double[] p = {ufo[id][0]/norm, ufo[id][1]/norm};
				for(int i=0;i<n;i++){
					if(u[i])continue;
					double[] ci = {ufo[i][0], ufo[i][1]};
					double A = dot(p, p);
					double B = -2*dot(p, ci);
					double C = dot(ci, ci)-ufo[i][2]*ufo[i][2];
					double D = B*B-4*A*C;
					if(D>=0){
						double t1 = (-B-Math.sqrt(D))/(2*A);
						double t2 = (-B+Math.sqrt(D))/(2*A);
						if(t1>R||t2>R)u[i] = true;
					}
					ufo[i][0] += adv[i][0];
					ufo[i][1] += adv[i][1];
					dist[i] -= ufo[i][3];
				}
			}
			System.out.println(c);
		}
	}
	
	public static void main(String[] args) {
		new AOJ0204().run();
	}
}