격자 L의 * C가 N 사각형의 좌표 (N < = 100.000) (L 및 C는 0 내지 1.000.000.000 범위 일 수있다) I 겹치는 사각형의 최대 수를 알고 싶어 주어 그리드의 어느 지점에서든. 최대 사각형이 중첩 지점
그래서 나는, 내가 추가하거나 내 구조에 간격을 제거 x 값으로 분류되어 각 이벤트 (사각형의 개방 또는 종료)를 들어, 청소 알고리즘을 사용하는 것이 생각.나는 간격의 최대 중첩을 유지하고 추가하고 간격을 제거 할 수 있도록 나무를 사용해야합니다.
간격 (시작 및 끝) 값이 0에서 100.000까지 인 경우이를 수행하는 방법을 알고 있지만 평면의 크기가 0에서 1.000.000.000까지이므로 여기서는 불가능합니다. 그런 나무를 어떻게 구현할 수 있습니까?
이 선행 모든 사각형의 좌표를 알고 있다면, 당신은 "압축 좌표"를 사용할 수 있습니다.
10^5 개의 직사각형 만 있으므로 x과 y 좌표가 최대 2 * 10^5입니다. 따라서 좌표 값을 1에서 2 * 10^5까지의 자연수 (좌표 정렬만으로)로 매핑 할 수 있습니다. 그런 다음 새로운 좌표에 대해 이미 알고있는 일반 트리를 사용할 수 있습니다.
이것은 직사각형 수를 얻는 데 충분하지만, 겹치는 위치가 필요할 경우 직사각형의 실제 좌표로 돌아갈 수 있도록 역 매핑을 유지해야합니다. 일반적인 경우 대답은 단일 지점이 아닌 직사각형입니다.
좋아,이 구현하려고 할 이해하지만 역방향 매핑을 수행하는 것은 매우 까다로운 것으로 보인다. 그러나 좋은 해결책입니다. – user1637030
실제로는 꽤 쉽습니다. 보통에서 압축에 이르기까지 일종의 사전 (맵 등)을 사용하고 역 매핑의 경우 "3 번째 비 - 압축 된 x 좌표는 198 "입니다. 나무를 구현하는 데 익숙하다면 큰 부담이되지 않습니다. –
사용 interval tree. 귀하의 경우는 조금 더 복잡합니다. 그 이유는 가중치가있는 간격 트리가 실제로 필요하기 때문입니다. 여기서 가중치는 해당 간격의 열린 직사각형 수입니다.
매우 복잡한 나무처럼 보입니다. 이런 식으로 사용하지는 않겠지 만, 나는 이것을 연구 할 것이지만, 위키피디아보다 더 나은 튜토리얼을 가지고 있니? – user1637030
미안하지만. –
는 L과 C 정수 있습니까? –
조회가 얼마나 빨리 필요합니까? O (1) 검색을하기 위해 미리 쓸어 버리고 싶은 것 같습니다. 알고 자하는 각 점에 대해 직사각형을 스캔하는 것은 허용되지 않습니까? – mprivat
예 L 및 C 정수 – user1637030