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_bound
、upper_bound
、distance
が使われてるのが大きいかな
ここは自前でやったからまあ
下限を求めるところももうちょっとスマートにやれそうな気はしている
lower_bound
は実装したけどもうちょっとシンプルになるような気がする
upper_bound
は実装できるだろうけど、そうしたところで
distance
を求めるときに順にたどっていく以外の方法が思いつかなかったので
lower_bound
からひとつずつ数えていくコードのままにしている
本のコードでは番兵を入れているんだけどちょっと意味が分からない
C++のライブラリは普通の二分探索木とは違うんだろか
そもそもset<int>
だしなあ
あとEP.append(EndPoint(s.p2, s, EPStatus.RIGHT))
の行はいらない
右端の点は、左端のEndPoint
のseg
から持ってきてて参照されることがないから
ところで縦線同士・横線同士が端点でくっつくことはないんだっけ
数えてなくて気になってたけど目をつぶって提出したらACになったから
まあいいんだけど
でも問題文だけからそういうケースが除外できるかというとあんまり自信なし
そういうのは1本の線分とみなされるものなのかな