경계는

Question

내가이 문제를 해결하기 위해 효율적인 방법을 알고 싶어요의 사각형 :

A-왼쪽 상단과 오른쪽 하단을 부여 N 사각형을 감안할 때,의 둘레를 발견하십시오 N 개의 직사각형의 합집합.

난 단지 O(N^2) 알고리즘을 가지고 그렇게 더 효율적인 알고리즘을 찾아주십시오, 너무 느린.

해당 값은 양의 정수 미만 100000 좌표 취할 수

EDIT : 예를 들어,이 경우, 경계는 30

오 (n은^2) 알고리즘 :

for x=0 to maxx 
    for i=0 to N 
     if lowx[i] = x 
     for j=lowy[i] to highy[i] 
      d[j]++ 
      if d[j] = 1 then ret++ 
     if highy[i] = x 
     for j=lowy[i] to highy[i] 
      d[j]-- 
      if d[j] = 0 then ret++ 
    for y=0 to maxy 
     if d[y] = 0 && d[y + 1] >= 1 then ret++ 
     if d[y] >= 1 && d[y + 1] = 0 then ret++ 

최종 답변이 답변입니다.

Answer 1

한편으로이 문제에 대한 고전적 해결책은 원래 형태로이 직사각형의 합집합을 구축하는 즉 결과의 다각형 경계를 만드는 스윕 라인 기반 "부울 병합"알고리즘입니다. 알고리즘은 물리적으로 구축하지 않고 결과 경계의 둘레를 계산하도록 쉽게 수정할 수 있습니다.

반면에 스윕 라인 기반 "부울 병합"은 임의의 다각형 입력에 대해이를 수행 할 수 있습니다. 귀하의 경우 입력이 훨씬 더 제한된 (그리고 단순화 된) - 단지 여러개의 등각 직사각형이 있음을 감안할 때, 더 가볍고 똑똑한 솔루션이 존재할 가능성이 큽니다.

참고로, 이러한 직사각형의 결합은 실제로 다중 연결 다각형, 즉 구멍이있는 영역 일 수 있습니다.

Answer 2

이 문제의 경우에 도움이 될이 그,

이 고려

_______ 
|  |_ 
|   | 
|  _| 
|___ | 
    | | 
    |___| 

이 같은 경계가 있습니다

_________ 
|   | 
|   | 
|   | 
|   | 
|   | 
|_________| 

Answer 3

오 거기를 (N 로그 n) - 시간 스위프 라인 알고리즘. 모양의 수직 둘레를 계산하려면 다음 단계를 적용하십시오. 입력을 조 변경하고 다시 적용하여 수평 둘레를 계산하십시오.

각 사각형에 대해 값이 y 간격 인 왼쪽 x 좌표로 시작 이벤트를 준비하고 값이 y 간격 인 오른쪽 x 좌표로 중지 이벤트를 준비하십시오. 이러한 이벤트를 x 좌표로 정렬하고 순서대로 처리하십시오. 항상 경계가 횡선과 교차하는 지점 수를보고 할 수있는 데이터 구조를 유지합니다. 이벤트 포인트 간의 2n-1 간격에서이 수를 간격의 너비에 둘레로 곱합니다.

필요한 데이터 구조는 시간 O (log n)에서 다음 작업을 지원합니다.입력 된 좌표 값이 정수로 묶여 있기 때문에

insert(ymin, ymax) -- inserts the interval [ymin, ymax] into the data structure 
delete(ymin, ymax) -- deletes the interval [ymin, ymax] from the data structure 
perimeter() -- returns the perimeter of the 1D union of the contained intervals 

는 하나의 가능한 구현은 segment tree 통해이다. (입력의 y 좌표를 선별 작은 정수로 맵핑 관련된 실제의 입력에 대한 확장이있다.) 각 세그먼트는 어떤 관련 데이터

struct { 
    int covers_segment; 
    bool covers_lower; 
    int interior_perimeter; 
    bool covers_upper; 
}; 

그 범위 인 부분의 조합이 있다는 것이 후손을 갖는다 입력 간격에 표시됩니다. 매우 긴 세그먼트는 트리의 가장 잎 수준에 영향을주지 않습니다.

covers_segment의 의미는이 세그먼트가 분해되는 간격의 수입니다. covers_lower의 의미는 동일한 하위 끝 점이있는 세그먼트에서 나온 세그먼트 중 하나가 일정 간격의 분해에 속하면 사실입니다. interior_perimeter의 의미는 범위에있는 세그먼트의 1D 경계입니다 (위에서 설명한대로). covers_upper의 의미는 상위 끝점 인 covers_lower과 유사합니다.

다음은 예입니다.

0 1 2 3 4 5 6 7 8 9 

[---A---] 
    [---B---] [-D-] 
     [-C-] 

간격 A ([0, 4]) 및 B ([2, 4], [4, 6]) 및 C [3, 4] [4, 5] 및 D [7, 8] [8, 9]이다.

   c_s c_l i_p c_u 
[0, 1]   0 F 0 F 
    [0, 2]  0 F 0 F 
[1, 2]   0 F 0 F 
    [0, 4]  1 T 0 T 
[2, 3]   0 F 0 F 
    [2, 4]  1 T 1 T 
[3, 4]   1 T 0 T 
     [0, 8] 0 T 2 F 
[4, 5]   1 T 0 T 
    [4, 6]  1 T 1 T 
[5, 6]   0 F 0 F 
    [4, 8]  0 T 2 F 
[6, 7]   0 F 0 F 
    [6, 8]  0 F 1 F 
[7, 8]   1 T 0 T 
     [0, 9] 0 T 2 T 
[8, 9]   1 T 0 T 

는 (감소하는) covers_segment을 증가시켜 그 구성 부분을 삽입 (삭제) 구간을 삽입 (삭제)한다. 그런 다음 영향을받은 세그먼트의 모든 조상에 대해 다음과 같이 다른 필드를 다시 계산하십시오.

if s.covers_segment == 0: 
    s.covers_lower = s.lower_child.covers_lower 
    s.interior_perimeter = 
     s.lower_child.interior_perimeter + 
     (1 if s.lower_child.covers_upper != s.upper_child.covers_lower else 0) + 
     s.upper_child.interior_perimeter 
    s.covers_upper = s.upper_child.covers_upper 
else: 
    s.covers_lower = true 
    s.interior_perimeter = 0 
    s.covers_upper = true 

는 perimeter을 구현 root 세그먼트 트리의 루트입니다

(1 if root.covers_lower else 0) + 
root.interior_perimeter + 
(1 if root.covers_upper else 0) 

돌아갑니다.