CGL_3_C: Polygon-Point Containment (続き2)

このへんで時間切れ

次はちょうど頂点を通過する場合

        self.assertEqual(p.contains(Point(6,3)), CN.INSIDE)
        self.assertEqual(p.contains(Point(0,5)), CN.OUTSIDE)
        self.assertEqual(p.contains(Point(4,5)), CN.OUTSIDE)

今のやりかたのまま、単純にintersectsするかどうかで考えると
ふたつの辺を(端っこで)通ると判定されることになる
これはなんとなくよくなさそうな予感
2回通るとカウントされると、今のアルゴリズムではその頂点はなかったものと同じ

始点は数えるけど終点は数えないとかそんな感じにやるといいかな？
えーと
ちょうど頂点を通過する場合、図形的に考えるとふたつのケースがある
半直線が辺を横切る形になる場合と、頂点をかすめる形になる場合
頂点をかすめる形になる場合は内外に影響しないからなかったことになってもいいけど
横切る場合は1回とカウントしなければいけない

区別をつけようとするとどうすればいい
もうひとつ先の辺まで読めばいいわけだけど必須かな
必須だな
先読みするとなるとジェネレータっぽくないんだよなー
せっかくジェネレータ書いたのになー
もうちょっとシンプルなやり方ないかなー
おもいつかないなー

書いてみる
終点は数えるけど始点は数えない、の方が書きやすいかな
といってもかなり無理くり感出てきた

    def contains(self, p: Point) -> Containment:
        ps = Segment(p, Point(100000.0, p.y))
        count = 0
        for k in range(self.n):
            p1 = self.vertices[k]
            p2 = self.vertices[self.next(k)]
            s = Segment(p1, p2)
            if p.location(s) == PointLocation.ON_SEGMENT:
                return Containment.ONLINE
            p3 = self.vertices[self.next(self.next(k))]
            if p.x < p1.x and float_equal(p.y, p1.y):
                continue
            if p.x < p2.x and float_equal(p.y, p2.y):
                if p1.y < p2.y < p3.y or p1.y > p2.y > p3.y:
                    count += 1
            elif ps.intersects(s):
                count += 1
        return Containment.OUTSIDE if count % 2 == 0 \
            else Containment.INSIDE

あらためて考えてみると上のテストケース、
外部→頂点→外部とかすめる場合と内部→頂点→外部で横切る場合はカバーしてるけど
内部→頂点→内部とかすめる場合や外部→頂点→内部と横切る場合がカバーできてないな
コード上のカバレッジ的には全部通るけど
こういうのはどうなのかね
コードが不足しているってわけでもないけど図形的に考えるとカバーできてないという

えーとあとは半直線と辺が重なるパターン
これはなかったことにすればよさそうだ
すこし条件を付け足せばいいかな・・・
っていうかあれ？
もしかしてこのままで通る？

最後の封印を解除
アンスラサクスが出てきそうだな

        self.assertEqual(p.contains(Point(0,1)), CN.OUTSIDE)
        self.assertEqual(p.contains(Point(0,3)), CN.OUTSIDE)
        self.assertEqual(p.contains(Point(2,3)), CN.INSIDE)

通っちゃった
てことはこれでmainを書けばジャッジが通るってことなのか？
そうなのか？
（あんまりそんな気がしていない）

mainはこう

def main() -> None:
    n = int(input())
    points = []
    for i in range(n):
        x, y = [int(x) for x in input().split()]
        points.append(Point(x, y))
    polygon = Polygon(points)

    q = int(input())
    for i in range(q):
        x, y = [int(x) for x in input().split()]
        print(int(polygon.contains(Point(x, y))))

ジャッジ
#10でWA
そうですか

どこで間違ったかな
って32角形とかやめて
泣きながら方眼紙に図形をトレースする（泣いてない

あーなるほど
終点が半直線上にあって、その次の線分がx軸に平行な場合か
なるほどね
もうひとつ先まで見に行かないと決まらないのか