CGL_2_B: Intersection
今度は線分が交差するかを判定する問題
線分が交点を持つかどうかは線分の距離を求めるときに外積でやった
副作用的に
でもこの問題のヒントはCounter Clockwiseの絵になってる
えーと
p0からp1を見たときにp2とp3が反対側にあって、
p2からp3を見たときにp2とp3が反対側にあればいいのか
なるほど
でもそっちで書く前にとりあえず外積版を使ってやってみる
こんな感じ
def main() -> None:
q = int(input())
for _ in range(q):
x0, y0, x1, y1, x2, y2, x3, y3 = \
[int(x) for x in input().split()]
s1 = Segment(Point(x0, y0), Point(x1, y1))
s2 = Segment(Point(x0, y0), Point(x1, y1))
print(1 if s1.intersects(s2) else 0)
どれ
# 1 RE
ZeroDivisionError: division by zero
うぐ
あーそうだった
交わるかどうかの判定にまず平行かどうかを入れたほうがいいかな
あ、平行とか重なるとか考慮するの忘れてた
そういう判定入れると面倒、っていうか
Counter Clockwiseとおんなじことになる?
やっぱりCounter Clockwise使うほうが楽か
ところで重なってる場合って交差してるって言う?
とか先端がちょうど相手の線分上とか
交差の定義が共有する点を持つ、なら交差だな
そういうテストパターンもあるだろう
is_parallelの判定だけいれてちょっとだけ試してみよう
def intersects(self, other: 'Segment') -> bool:
if self.is_parallel(other):
return False
s, t = self.intersect_ratio(other)
return (0 <= s <= 1) and (0 <= t <= 1)
これだと重なる場合で間違えるはず・・・
0 0 5 0 5 0 7 0
で間違えた
端っこでくっついてるケースか
これは交差してることにしないといけないわけだな
了解した
Counter ClockwiseでもONLINE_*やON_SEGMENTのときを
考慮しておかないといけない
ON_SEGMENTはつまりその点で交差してるわけだから交差
両方ON_SEGMENTでも・・いいよな
ONLINE_*だったら交差しない・・・
いやそんなことないな
ONLINE_FRONTと、ONLINE_BACKまたはON_SEGMENTだとか
ONLINE_BACKと、ONLINE_FRONTまたはON_SEGMENTなら交差する
意外とややこしいぞ
全部の可能性を考えると54かちょっと無理
同一直線上にあるかどうかでまず分けて・・・
- 同一直線上にある場合
- O_FとO_F、O_BとO_Bになる場合 → 共有点を持たない
- O_BとO_S、O_SとO_Fになる場合 → 共有点を持つ(一部が重なる)
- O_FとO_B、O_SとO_Sになる場合 → 共有点を持つ(一方が他方を含む)
- 同一直線上にない場合
こうですかわかりません
これをコードにするのもなかなか・・・
こ、こうでしょうか?
def intersects(self, other: 'Segment') -> bool:
d0 = self.p1.location(other)
d1 = self.p2.location(other)
if {d0, d1} in [{PL.O_B, PL.O_S},
{PL.O_S, PL.O_F},
{PL.O_F, PL.O_B},
{PL.O_S, PL.O_S}]:
return True
if {d0, d1} in [{PL.O_F, PL.O_F},
{PL.O_B, PL.O_B},
{PL.CW, PL.CW},
{PL.CW, PL.O_F},
{PL.CW, PL.O_B},
{PL.CCW, PL.CCW},
{PL.CCW, PL.O_F},
{PL.CCW, PL.O_B}]:
return False
d2 = other.p1.location(self)
d3 = other.p2.location(self)
if {d2, d3} in [{PL.CW, PL.CW},
{PL.CW, PL.O_F},
{PL.CW, PL.O_B},
{PL.CCW, PL.CCW},
{PL.CCW, PL.O_F},
{PL.CCW, PL.O_B}]:
return False
return True
いちおうAC出たな
しかしそれでも本当に正しいコードを書けたという自信が持てない
解説にこんなコードが載ってるとも思えない