TOYPRO解説 夏の超大三角 (400点)


これは競プロ形式のPython学習サービス「TOYPRO(トイプロ)」の練習問題のうちの一つ,「夏の超大三角」 (400点問題)の解説です.

問題文(一部省略)

星空を二次元の座標系に見立てたとき、ベガの座標$(x_1,y_1)$、デネブの座標$(x_2,y_2)$、アルタイルの座標$(x_3,y_3)$、エックスの座標$(x_4,y_4)$が与えられます。
ベガ、デネブ、アルタイルを結んでできる三角形の面積と、ベガ、デネブ、エックスを結んでできる三角形の面積の、どちらが大きいかを判定するプログラムを作成してください。

出力

ベガ、デネブ、エックスを結んでできる三角形の面積のほうが大きい場合は"Yes"、ベガ、デネブ、アルタイルを結んでできる三角形の面積のほうが大きい場合は"No"、二つの三角形の面積が等しい場合は"Equal"と出力してください。

制約

$-100 \leq x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4 \leq 100$

解説

解法2が一番シンプルだと思います(ただし,高校数学のベクトルの知識を使う).

解法1 算数チックに解く

 図のように,三角形の面積は,大きな長方形の面積から余分な三角形の面積を引いたものである,ということを使って解くことができます.

 まず,ベガ,デネブ,アルタイルを結んでできる三角形を考えます.
このとき,図で言うとまわりの大きな長方形の横の長さは,$|x_1-x_2|,|x_1-x_3|,|x_2-x_3|$のうち最大のものです.同様に,縦の長さは,$|y_1-y_2|,|y_1-y_3|,|y_2-y_3|$のうち最大のものです.
(※注,$||$は「絶対値」の記号で,中身が0以上ならそのまま,マイナスならマイナスを取り除いた値を表します.例えば,$|5|=5$,$|-3|=3$,$|2-7|=5$です.要は数直線上での(0との)「距離」です.(小学生向け))
 また,3つの余分な三角形の面積は,それぞれ三角形の辺ごとに考えて
$|x_1-x_2||y_1-y_2|\div2$, $|x_1-x_3||y_1-y_3|\div2$, $|x_2-x_3||y_2-y_3|\div2$
すなわち
$|(x_1-x_2)(y_1-y_2)|\div2$, $|(x_1-x_3)(y_1-y_3)|\div2$, $|(x_2-x_3)(y_2-y_3)|\div2$ となります.
これらは,紙に図を書いたりすると分かりやすいかもしれません.

 次に,ベガ,デネブ,エックスを結んでできる三角形を考えます.
大きな長方形の横の長さは,先ほどと同様に,$|x_1-x_2|,|x_1-x_4|,|x_2-x_4|$ のうち最大のもの,縦の長さは,$|y_1-y_2|,|y_1-y_4|,|y_2-y_4|$ のうち最大のものです.
 また,3つの余分な三角形の面積も先ほどと同様に,それぞれ
$|(x_1-x_2)(y_1-y_2)|\div2$, $|(x_1-x_4)(y_1-y_4)|\div2$, $|(x_2-x_4)(y_2-y_4)|\div2$ となります.

 以上により,最大を表す関数max()と絶対値を表す関数abs()を使って,実装例は次のようになります.(まあ,max()abs()を知らなくても最悪if文・for文を使って書けますが,使ったほうが便利です.)

# 入力
x1 = 0
y1 = 0
x2 = 4
y2 = 0
x3 = 0
y3 = 2
x4 = 0
y4 = 2

# もとの三角形
W1=max(abs(x1-x2),abs(x1-x3),abs(x2-x3))  # 大きな長方形の横の長さ
H1=max(abs(y1-y2),abs(y1-y3),abs(y2-y3))  # 大きな長方形の縦の長さ
T1=(abs((x1-x2)*(y1-y2))+abs((x1-x3)*(y1-y3))+abs((x2-x3)*(y2-y3)))/2  # 余分な三角形の面積の和
S1=W1*H1-T1  # もとの三角形の面積

# 新しい三角形
W2=max(abs(x1-x2),abs(x1-x4),abs(x2-x4))  # 大きな長方形の横の長さ
H2=max(abs(y1-y2),abs(y1-y3),abs(y2-y3))  # 大きな長方形の横の長さ
T2=(abs((x1-x2)*(y1-y2))+abs((x1-x4)*(y1-y4))+abs((x2-x4)*(y2-y4)))/2  # 余分な三角形の面積の和
S2=W2*H2-T2  # 新しい三角形の面積

# 出力
if S1<S2:
    print("Yes")
elif S1==S2:
    print("Equal")
else:
    print("No")

解法2 ベクトルを用いた三角形の面積の公式を使う

三角形 $OAB$ において,$\overrightarrow{OA}=(a_1,a_2), \overrightarrow{OB}=(b_1,b_2)$としたとき,三角形 $OAB$ の面積 $S$ は
$$S=\frac{1}{2}|a_1b_2-a_2b_1|$$
となることを使って,解くことができます.
一番シンプルな解法だと思います.
実装例は次のようになります.

# 入力
x1 = 0
y1 = 0
x2 = 4
y2 = 0
x3 = 0
y3 = 2
x4 = 0
y4 = 2

S1=abs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1))  # (もとの三角形の面積)*2
S2=abs((x2-x1)*(y4-y1)-(x4-x1)*(y2-y1))  # (新しい三角形の面積)*2

# 出力
if S1<S2:
    print("Yes")
elif S1==S2:
    print("Equal")
else:
    print("No")

おまけ(嘘解法?)

 ヘロンの公式を使いたくなった人もいると思います.

ヘロンの公式ってなんだし?

三辺の長さが $a,b,c$ の長さの三角形の面積 $S$ は, $s=\frac{a+b+c}{2}$ として,
$$S=\sqrt{s(s-a)(s-b)(s-c)}$$

# 入力
x1 = 0
y1 = 0
x2 = 4
y2 = 0
x3 = 0
y3 = 2
x4 = 0
y4 = 2

a=((x1-x2)**2+(y1-y2)**2)**0.5  # ベガ・デネブ間の距離
b=((x1-x3)**2+(y1-y3)**2)**0.5  # ベガ・アルタイル間の距離
c=((x2-x3)**2+(y2-y3)**2)**0.5  # デネブ・アルタイル間の距離
d=((x1-x4)**2+(y1-y4)**2)**0.5  # ベガ・エックス間の距離
e=((x2-x4)**2+(y2-y4)**2)**0.5  # デネブ・エックス間の距離

# ヘロンの公式

s=(a+b+c)/2
S1=s*(s-a)*(s-b)*(s-c) # もとの三角形の面積の2乗(辺はa,b,c)

s=(a+d+e)/2
S2=s*(s-a)*(s-d)*(s-e)  # 新しい三角形の面積の2乗(辺はa,d,e)

# 出力
if S1<S2:
    print("Yes")
elif S1==S2:
    print("Equal")
else:
    print("No")

(注・$\sqrt{a}=a^{\frac{1}{2}}=a^{0.5}$を使ってコードを書いています)

しかし,次のようなケースではどうなるでしょうか.

x1 = -100
y1 = -100
x2 = -100
y2 = 100
x3 = 100
y3 = 99
x4 = 100
y4 = 0

図を書いていただくとわかるように,$S_1$をもとの三角形の面積,$S_2$を新しい三角形の面積とすると,$S_1=S_2$なので"Equal"と出力されるはずですが…

??????
なんで?
ということで,今度は$S_1,S_2$の値も出力してみましょう.

$S_1$の値にいくらか誤差が出てしまっています.
どうしてこうなるかというと,星と星との間の距離を出したときに三平方の定理で平方根を取ったため,浮動小数点型(float型)の誤差が出ているためです.ちなみに,これはmath.sqrt()を使っても同様です.
浮動小数点型(float型)の誤差には気をつけましょう.

でもTOYPROでは通る(テストケースがゆるいやさしい競プロサイトなので)


しかし,AtCoder等の外部競プロサイトではまず落とされると思いますのでそのときには気をつけましょう.

終わりに

最後までご覧いただきありがとうございました.これは初めての競プロ解説記事であるため,至らないところも多々あったと思いますが,今後ともよろしくお願いします.
記事のミス,直すべき箇所等があった場合,コメントまたはTwitter(@MUSUKA0605)に報告して頂けると嬉しいです.