kb84tkhrのブログ

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

CGL_2_B: Intersection

PCAD

今度は線分が交差するかを判定する問題
線分が交点を持つかどうかは線分の距離を求めるときに外積でやった
副作用的に

でもこの問題のヒントは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になる場合 → 共有点を持つ（一方が他方を含む）
  • 同一直線上にない場合
    • どちらかがCWと(CW|O_F|O_S)になる場合 → 共有点を持たない
    • どちらかがCCWと(CCW|O_F|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出たな
しかしそれでも本当に正しいコードを書けたという自信が持てない
解説にこんなコードが載ってるとも思えない