CGL_1_C: Counter-Clockwise
Counter-Clockwiseという名前だけど
平面上に(向きのある)線分p0p1と点p2が与えられ、線分と点の位置関係を
求める問題、と言ったほうがいいかも
- 点が線分の左側にある
- 点が線分の右側にある
- 点が線分の手前にある
- 点が線分の向こうにある
- 点が線分上にある
右か左か線分(の延長)上かは外積を使えばわかる
直線上だったら比を求めればいいだろう
これくらいなら思考★でも納得感
引数は3点であたえるべきか線分と点で与えるべきか
決めるにはちょっと材料が不足している気もするのでえいやで後者
そういえばPythonでenum的なものってどうやって書くんだったかな
enum.Enumを継承すればいいのか
この問題でEnumを使うべきかという話はなくもない
問題にCOUNTER_CLOCKWISEが1っぽく書いてある意味もあまりないけど
class PointLocation(Enum):
COUNTER_CLOCKWISE = 1
CLOCKWISE = 2
ONLINE_BACK = 3
ONLINE__FRONT = 4
ONLINE_SEGMENT = 5
判定
def location(self, seg: 'Segment') -> PointLocation:
p = self - seg.p1
d = seg.vector().cross(p)
if d < 0:
return PointLocation.CLOCKWISE
elif d > 0:
return PointLocation.COUNTER_CLOCKWISE
else:
if seg.p2.x != seg.p1.x:
r = (self.x - seg.p1.x) / (seg.p2.x - seg.p1.x)
else:
r = (self.y - seg.p1.y) / (seg.p2.y - seg.p1.y)
if r < 0:
return PointLocation.ONLINE_BACK
elif r > 1:
return PointLocation.ONLINE_FRONT
else:
return PointLocation.ON_SEGMENT
ちょいと長たらしい
直線上にあるときを別関数に出してもいいけどあんまり必然性を感じない
直線上にある場合は、y軸に平行なときだけ場合分け
もっとすっきりいかないものか
Pythonにswitch的なのがないのはちょっと気に食わないところ
ないよね?
おかげでdとかrとか一時変数が必要に
判定ができればあとは簡単
def main() -> None:
x0, y0, x1, y1 = [int(x) for x in input().split()]
s = Segment(Point(x0, y0), Point(x1, y1))
q = int(input())
for _ in range(q):
x2, y2 = [int(x) for x in input().split()]
print(Point(x2, y2).location(s).name)
Enumは.name
で名前が取れるところがミソ
.value
で値も取れる
さてジャッジ
AC
あれ
AC取れるつもりはなかった
if d < 0:
elif d > 0:
else:
でぴったり0にならなくてelseに入りそこねる入力も
あるんじゃないかと思ってたんだけどなあ
WAが出てから修正するつもりだったのに
でも修正
def location(self, seg: 'Segment') -> PointLocation:
p = self - seg.p1
d = seg.vector().cross(p)
if float_equal(d, 0.0):
if seg.p2.x != seg.p1.x:
r = (self.x - seg.p1.x) / (seg.p2.x - seg.p1.x)
else:
r = (self.y - seg.p1.y) / (seg.p2.y - seg.p1.y)
if r < 0:
return PointLocation.ONLINE_BACK
elif r > 1:
return PointLocation.ONLINE_FRONT
else:
return PointLocation.ON_SEGMENT
elif d > 0:
return PointLocation.COUNTER_CLOCKWISE
else:
return PointLocation.CLOCKWISE
さらに見づらく