九州大学 1999年 文系 第8問 解説

方針・初手

座標平面上の点と直線の距離の公式、および直線の方程式を用いた領域の正負の判定を BASIC のプログラムとして記述する問題である。 数学的な公式を立式し、それを BASIC の文法（絶対値関数 ABS、平方根関数 SQR、論理演算、条件分岐 IF 文など）を用いて表現する。

解法1

(1)

原点 $O(0,0)$ と点 $A(a_1, a_2)$ を通る直線 $OA$ の方程式は、

$$a_2 x - a_1 y = 0$$

と表される。 点 $P(p_1, p_2)$ からこの直線 $OA$ までの距離 $d$ は、点と直線の距離の公式により、

$$d = \frac{|a_2 p_1 - a_1 p_2|}{\sqrt{a_1^2 + a_2^2}}$$

となる。問題の条件より $O$ と $A$ は異なる点であるから、$a_1^2 + a_2^2 \neq 0$ であり分母が $0$ になることはない。 これを BASIC の計算式で記述する。平方根には SQR 関数、絶対値には ABS 関数を用いる。距離 $d$ を計算して変数 D に代入し、PRINT 文で表示する。

(2)

2点 $A(a_1, a_2), B(b_1, b_2)$ を通る直線 $AB$ の方程式は、

$$(b_2 - a_2)(x - a_1) - (b_1 - a_1)(y - a_2) = 0$$

と表される。 ここで、$x$ の係数と $y$ の係数をそれぞれ $X = b_1 - a_1, Y = b_2 - a_2$ とおき、平面上の点 $(x, y)$ に対して関数 $f(x, y)$ を

$$f(x, y) = Y(x - a_1) - X(y - a_2)$$

と定義する。 直線 $AB$ の法線ベクトルの大きさは $L = \sqrt{X^2 + Y^2}$ であり、$A$ と $B$ は相異なる点であるため $L > 0$ である。 任意の点 $R(x, y)$ と直線 $AB$ との距離 $d$ は、

$$d = \frac{|f(x, y)|}{L}$$

となる。 点 $P(p_1, p_2)$ について $U = f(p_1, p_2)$、点 $Q(q_1, q_2)$ について $V = f(q_1, q_2)$ とする。 点 $P$ または点 $Q$ が直線 $AB$ 上にあるとみなされる条件は、それぞれの点と直線の距離が EPS より小さいことである。すなわち、

$$\frac{|U|}{L} < \text{EPS} \quad \text{または} \quad \frac{|V|}{L} < \text{EPS}$$

が成り立つとき、問題の指示に従い 0 を表示する。プログラム上では割り算による誤差やゼロ除算を避けるため、両辺に $L$ を掛けて $|U| < \text{EPS} \cdot L$ または $|V| < \text{EPS} \cdot L$ として判定するのがよい。

両方の点が直線上にあるとみなされない場合、点 $P, Q$ が直線 $AB$ に対し同じ側にある条件は $U \cdot V > 0$ であり、このとき 1 を表示する。 異なる側にある条件は $U \cdot V < 0$ であり、このとき -1 を表示する。

解説

数学の図形と方程式の知識をプログラミング言語に翻訳する融合問題である。 (2)において、直線の分割する領域が $f(x,y) > 0$ と $f(x,y) < 0$ の符号によって判別できるという性質（領域の正負）を用いると、条件分岐をすっきりと記述できる。 また、コンピュータにおける浮動小数点小数の誤差を考慮し、点と直線の距離が微小な値（EPS）以下である場合に「直線上にある」とみなす処理は、数値計算プログラムにおける典型的な手法である。

答え

(1)

方針 直線 $OA$ は方程式 $a_2 x - a_1 y = 0$ で表される。点 $P(p_1, p_2)$ から直線 $OA$ への距離 $d$ は $d = \frac{|a_2 p_1 - a_1 p_2|}{\sqrt{a_1^2 + a_2^2}}$ となるため、これをプログラム上の変数を用いて計算し表示する。

プログラム 40 D = ABS(A(2)*P(1) - A(1)*P(2)) / SQR(A(1)*A(1) + A(2)*A(2)) 50 PRINT D 60 END

(2)

方針 直線 $AB$ の方程式は $(b_2 - a_2)(x - a_1) - (b_1 - a_1)(y - a_2) = 0$ である。 $f(x, y) = (b_2 - a_2)(x - a_1) - (b_1 - a_1)(y - a_2)$ とし、$L = \sqrt{(b_1 - a_1)^2 + (b_2 - a_2)^2}$ とする。点 $(x, y)$ と直線の距離は $\frac{|f(x,y)|}{L}$ で与えられる。 $U = f(p_1, p_2), V = f(q_1, q_2)$ と計算し、$\frac{|U|}{L} < \text{EPS}$ または $\frac{|V|}{L} < \text{EPS}$ のときは 0 を表示する。そうでないとき、$UV > 0$ ならば 1 を、$UV < 0$ ならば -1 を表示する。

プログラム 70 X = B(1) - A(1) 80 Y = B(2) - A(2) 90 L = SQR(XX + YY) 100 U = Y*(P(1) - A(1)) - X*(P(2) - A(2)) 110 V = Y*(Q(1) - A(1)) - X*(Q(2) - A(2)) 120 IF ABS(U) < EPSL OR ABS(V) < EPSL THEN PRINT 0 : GOTO 150 130 IF UV > 0 THEN PRINT 1 140 IF UV < 0 THEN PRINT -1 150 END