kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

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みたいなのも作ったっけな?
とかやってるあいだにおねむの時間だ
続きは明日