パソコン甲子園の問題ってムズくね。

ティーチャーは「基本的な問題」とおっしゃるが、これが基本的な問題ならばオレはやはりまだまだ初心者ということである。問題の中にはJavaやVB.NETなどの基本ライブラリが充実した言語の方が明らかにプログラミングしやすいものもあり、C言語しか使えない俺にとっては風当たりも強いのだが頑張ろう。夏はまだ始まったばかりである。

で、2006年度予選(pdf)の例題7を解くためのアルゴリズムをぐだぐだと無い頭で考えた。オレは数学嫌いじゃないけど苦手である。だから世の中にはもっとエレガントな方法があるに違いないが、とりあえずはこれで妥協。

問題

線分PQと円Oの共有点が存在するかどうか*1

入力

円Oの中心点の座標(Ox, Oy)、円Oの半径r、点Pの座標(Px, Py)、点Qの座標(Qx, Qy)

解法

1. 直線PQの式を求める

公式より

$y = \frac{Qy - Py}{Qx - Px}(x - Px) + Py$

また、

$a = \frac{Qy - Py}{Qx - Px}$
$b = Py - Px \frac{Qy - Py}{Qx - Px}$

とおくと

$y = ax + b$

と変形できる

2. 円Oの式を求める

円の方程式より

$(x - Ox)^2 + (y - Oy)^2 = r^2$

3. 組み合わせる

2.の円の式に1.の直線の式を代入すると

$(x - Ox)^2 + (ax + b - Oy)^2 - r^2 = 0$

展開・整理して

$(a^2 + 1)x^2 + 2(a(b - Oy) - Ox)x + (Ox^2 + (b - Oy)^2 - r^2) = 0$

こうして、二次方程式に持ち込むことができた。x以外の数値は既知であるから、あとはこれを頑張って解く

4. 仕上げ

3.の二次方程式の判別式が負であれば、円Oと線分PQの共有点は存在しない。もし判別式が正であるときは、点PQのx座標と解(共有点のx座標)の位置関係から答えを導く

5. 線分PQがy軸に平行な場合を忘れていないか

この場合は1.の直線の式がおかしなことになってしまうので、別の方法で解く必要がある。直線PQがy軸に平行であれば、その直線の式は

$x = Px$

となり、これを円Oの式に代入すると

$(y - Oy)^2 + (Px - Ox)^2 - r^2 = 0$

展開・整理して

$y^2 - 2(Oy)y + (Oy^2 + (Px - Ox)^2 - r^2) = 0$

となる。これを解くと共有点のy座標が出てくるので、あとは点PQのy座標との位置関係から答えを導けばよい。

というのをC言語で書くと

// 線分PQと円Oの共有点が存在するかどうか
int is_cross(int ox, int oy, int r, int px, int py, int qx, int qy)
{
	double p, q, a, b, c, d, x1, x2;
	
	// 線分がy軸に平行
	if (qx - px == 0) {
		a = 1.0;
		b = -oy;
		c = oy*oy + (px - ox)*(px - ox) - r*r;
		px = py; // 位置判定に使う
		qx = qy; // 位置判定に使う
	// それ以外
	} else {
		p = (double)(qy - py)/(qx - px);
		q = py - px * p;
		a = p*p + 1.0;
		b = p*(q - oy) - ox;
		c = ox*ox + (q - oy)*(q - oy) - r*r;
	}
	
	// 解の公式
	d = b*b - a*c;
	x1 = (-b + sqrt(d))/a;
	x2 = (-b - sqrt(d))/a;
	
	// 判別式
	if (d >= 0) {
		// 位置関係
		if ((x1 - px)*(x1 - qx) <= 0) return 1;
		else if ((x2 - px)*(x2 - qx) <= 0) return 1;
		else return 0;
	} else {
		return 0;
	}
}

変数名が分かりにくいので解説しておくと、p, q は直線の式 $y = ax+b$ の a, b の代わりで、a〜d は二次方程式 $ax^2 + bx + c = 0$ と判別式Dを表し、x1, x2 は二次方程式の解である。

また、位置関係のチェックは「円Oが点Pと点Qを隔てているか」を基準に行う。具体的には、共有点のx座標を x1、点P、Qのx座標をそれぞれ Px, Qx としたとき、x1 が Px と Qx の間にあれば共有点が存在し、そうでなければ共有点が存在しないことになる。数学的には(x1 - Px)と(x1 - Qx)の符合が異なれば共有点あり、符号が同じなら共有点なし、とすればいい。

*1:「直線PQと円Oの共有点」ならただ「点と直線の距離」の公式を適用するだけでいいと思うんだけど、「線分PQ」だからそうはいかない。つまり、ちゃんと二次方程式を解いて、共有点の座標を出さないと答えは出ないはず