CGL_4_A: Convex Hull 続き
1日だけ考える
スタックとソートを使いそうなアイデアはあった
xを-10000から10000まで変化させつつ、y座標が最大・最小の点を
見つけていけば外周の候補にはなる
こんなことをしなくても、点をx座標でソートしてから順番に見ていけばいいもんね
順番に見ながら外周の可能性のある頂点をスタックに積みつつ
やっぱり外周じゃなかったらpopする
外周かどうかの判定は辺の外積でいいんじゃないか
スタックにp1、p2、p3と積まれてる状態で次がp4だとすると
p2p3とp3p4の外積が負ならp3をpopしてp1p2とp2p4の外積を計算、みたいな感じ
行けるんじゃないか
書いてみよう
from shape import Point
n = int(input())
P = []
for i in range(n):
x, y = [int(x) for x in input().split()]
P.append(Point(x, y))
P.sort()
S = []
S.append(P[0])
S.append(P[1])
for i in range(2, n):
えーと外積どうやって書いたっけ?
そういえばcounterclockwiseみたいなのも作ったっけな?
とかやってるあいだにおねむの時間だ
続きは明日