CGL_4_A: Convex Hull 続き2
忘れすぎてるので、なにやってたかだけでもおさらいする
pはPoint、vはVector、sはSegment、lはLine、cはCircle、PはPolygon
PointとVector、SegmentとLineは同じ型なので雰囲気で使い分け
型：Point, Vector, Segment, Line, Circle, Polygon
極座標：polar(a, r) -> p, p.arg()
ベクトルの基本演算： v1 + v2, v1 - v2, k * v (スカラー倍), v / k
ベクトルの大きさ： v.norm(), v.abs()
ベクトルの比較： v1 < v2, v1 == v2
内積(|a||b|cosθ)： v1.dot(v2)
外積(ax*by-ay*bx)：v1.cross(v2)
平行：v1.is_parallel(v2), l1.is_parallel(s2)
直行：v1.is_orthogonal(v2), l1.is_orthogonal(l2)
射影：l.projection(p)
反射：l.reflection(p)
点から直線への距離：p.distance_to_line(l)
点から線分への距離：p.distance_to_segment(s)
線分間の距離：s1.distance_with_segment(s2)
点と線分の位置関係（時計回り・反時計回り・・・）：p.location(s)
線分同士の交差判定：s1.intersects(s2)
線分の交点：s1.intersection(s2)
円と直線の交点：c.cross_point_line(l)
円同士の交点：c1.cross_point_circle(c2)
点の内包： pl.contains(p)
アルゴリズムまでは見直していない
で書いてみたら
おさらいしたけど実際使ったのは差と外積くらいだった
だいたい素直に書けたという感覚
[-1]しているのは重複を避けるため
def half_hull(P):
S = []
S.append(P[0])
S.append(P[1])
for i in range(2, n):
while len(S) > 1:
if (S[-1] - S[-2]).cross(P[i] - S[-1]) >= 0:
break
S.pop()
S.append(P[i])
return S
n = int(input())
P = []
for i in range(n):
x, y = [int(x) for x in input().split()]
P.append(Point(x, y))
A = half_hull(sorted(P, key=lambda p: (p.y, p.x)))[:-1] + \
half_hull(sorted(P, key=lambda p: (p.y, p.x), reverse=True))[:-1]
print(len(A), *A, sep='\n')AC
ヒントの矢印はX座標最小の点から始まってるけど、
求められてる解答はY座標最小の点から出力することになってるから
そこはヒントに逆らった
ソートも使ったしスタックも使ったし、行き帰りで2回やってるし
これはきっとテキストの解に近いのでは
S[-2]とかやっててスタックかよというツッコミはなしで
では見比べる
ほとんど同じだな（ということにしておこう
アンドリューのアルゴリズムと呼ぶ
