kb84tkhrのブログ

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

CGL_6_A: Segment Intersections: Manhattan Geometry 続き3

本と見比べる
大きな考え方は同じ
けどだいぶ短く見える

本のコードを見ながらpythonで書いてみる

from sys import stdin
from typing import Any, List, Optional
from enum import IntEnum

class EPStatus(IntEnum):
    BOTTOM = 0
    LEFT = 1
    RIGHT = 2
    TOP = 3

class EndPoint:
    def __init__(self, p: Point, seg: Segment, st: EPStatus):
        self.p = p
        self.seg = seg
        self.st = st

    def __lt__(self, other: "EndPoint") -> bool:
        return (
            self.st < other.st
            if self.p.y == other.p.y
            else self.p.y < other.p.y
        )

class Tree:

    ...

    def lower_bound(self, key: Any) -> Optional[Node]:
        x = self.root
        b: Optional[Node] = None

        while x is not None:
            if key < x.key:
                if b is None or x.key < b.key:
                    b = x
                x = x.left
            elif key == x.key:
                b = x
                break
            else:
                x = x.right

        return b

def manhattanIntersection(S: List[Segment]) -> int:
    def crosses(x1: float, x2: float) -> int:
        cnt: int = 0
        node: Optional[Node] = BT.lower_bound(x1)
        while node is not None and node.key <= x2:
            cnt += 1
            node = node.successor()
        return cnt

    EP: List[EndPoint] = []

    for s in S:
        if (s.p1.y == s.p2.y and s.p1.x > s.p2.x) or (
            s.p1.x == s.p2.x and s.p1.y > s.p2.y
        ):
            s.p1, s.p2 = s.p2, s.p1

        if s.p1.y == s.p2.y:
            EP.append(EndPoint(s.p1, s, EPStatus.LEFT))
            EP.append(EndPoint(s.p2, s, EPStatus.RIGHT))
        else:
            EP.append(EndPoint(s.p1, s, EPStatus.BOTTOM))
            EP.append(EndPoint(s.p2, s, EPStatus.TOP))

    EP.sort()

    BT = Tree()
    cnt = 0

    for e in EP:
        if e.st == EPStatus.TOP:
            BT.delete(BT.find(e.p.x))
        elif e.st == EPStatus.BOTTOM:
            BT.insert(Node(e.p.x))
        elif e.st == EPStatus.LEFT:
            cnt += crosses(e.seg.p1.x, e.seg.p2.x)

    return cnt

def main() -> None:
    S = []
    n = int(stdin.readline())
    for i in range(n):
        x1, y1, x2, y2 = [int(x) for x in stdin.readline().split()]
        S.append(Segment(Point(x1, y1), Point(x2, y2)))

    print(manhattanIntersection(S))

main()

思った以上にそっくりさんだった
違いは
線分を登録するのではなく線分の端点を登録する感じ
二分探索木には線分のx座標を登録しておけば足りる
なるほどな

あと長さに関しては交点の数を数えるところで
lower_boundupper_bounddistanceが使われてるのが大きいかな
ここは自前でやったからまあ
下限を求めるところももうちょっとスマートにやれそうな気はしている

lower_boundは実装したけどもうちょっとシンプルになるような気がする
upper_boundは実装できるだろうけど、そうしたところで
distanceを求めるときに順にたどっていく以外の方法が思いつかなかったので
lower_boundからひとつずつ数えていくコードのままにしている

本のコードでは番兵を入れているんだけどちょっと意味が分からない
C++のライブラリは普通の二分探索木とは違うんだろか
そもそもset<int>だしなあ

あとEP.append(EndPoint(s.p2, s, EPStatus.RIGHT))の行はいらない
右端の点は、左端のEndPointsegから持ってきてて参照されることがないから

ところで縦線同士・横線同士が端点でくっつくことはないんだっけ
数えてなくて気になってたけど目をつぶって提出したらACになったから
まあいいんだけど
でも問題文だけからそういうケースが除外できるかというとあんまり自信なし
そういうのは1本の線分とみなされるものなのかな