COUNTING 교차하는 코드 쌍 수

N 코드를 원으로 간주합니다. 각 코드는 끝점으로 결정됩니다. 원안 내부에서 교차하는 코드 쌍 수를 결정하기위한 해답을 O(nlogn)으로 설명하십시오.COUNTING 교차하는 코드 쌍 수

가정 사항 : 두 개의 코드가 끝점을 공유하지 않습니다.

2012-07-18 Kavish Dwivedi

숙제 태그가 누락 되었습니까? – BoBTFish

Google-fu : http://ripcrixalis.blog.com/2011/02/08/clrs-14-1-dynamic-order-statistics/ – biziclop

-1

내 머리 꼭대기에서 코드 끝점을 극좌표 각도로 정렬하십시오 (이것은 O (n log n) 부분입니다). 그런 다음 정렬 된 목록 (O (n))을 읽습니다. 두 개의 인접한 끝점이 동일한 코드에 속하면 교차점이 없습니다. 목록에있는 두 개의 인접 항목이 다른 코드에 속하는 경우 두 코드의 다른 끝점이 어디에 놓여 있는지에 따라 교차점이있을 수 있습니다. 화음 A가 끝점 A1과 A2를 소트 순서로 가지며, 마찬가지로 화음 B가 B1과 B2를 갖는 경우, B1이 더 빠르고 A2가 나중에 있기 때문에리스트에서 B2-A1을 찾은 것이 교차가 아닙니다. 그러나 B1-A2는 교차점이됩니다.

biziclop의 또 다른, 다소 신중하게 구성된 솔루션에 대한 설명을 참조하십시오.

출처

2012-07-18 15:20:40 twalberg

이렇게하면 일부 교차점을 찾을 수 있지만 모든 교차로를 찾지는 않습니다. 교차하는 코드는 교차로를 찾지 않습니다. 반드시 인접한 끝점을 가져야합니다. – interjay

불쌍한 말씨. 내가 말하고자하는 것은 하나의 특정 코드의 끝점에 정렬 된 순서로 다른 끝점이있는 경우 두 번째 코드의 끝 점이 첫 번째 끝점 사이에 있으면 교차점). A1, B1, C1, D1, A2와 같은 순서가 포함 된 경우를 고려하지 않았다고 생각합니다.이 경우 B, C, D 세 가지가 모두 교차합니다. – twalberg

그러나 이러한 교차점을 모두 ' O (n)'정렬 된 목록으로 이동하여 시간. 'O (n^2)'교차가있을 수 있기 때문에 'O (nlogn)'시간에 모든 교차점을 찾을 수 없습니다. 한 번에 여러 교차를 계산할 수있는 데이터 구조가 필요합니다. – interjay

O (nlogn)에서 작업을 수행하는 일반적인 선분 교차 알고리즘이 있습니다.
두 개의 코드가 원의 외부에서 교차 할 수 없기 때문에이 기능을 사용할 수 있습니다.
http://www.cs.princeton.edu/~chazelle/pubs/IntersectLineSegments.pdf

추신 :
다음 링크는 알고리즘을 포함
기본 계산 기하학에 대한 지식이 필요합니다 (선 스윕, 범위 트리).

희망이 도움이됩니다.

출처

2012-07-19 09:45:41

COUNTING 교차하는 코드 쌍 수

답변

관련 문제