수평선에서 3 점을 통과하는 교차 선을 찾으십시오.

Question

3 개의 수평선 (y = 0, y = 1, y = 2)으로 펼쳐지는 n 점의 그룹이 주어진다면 은 교차 선이 있는지 찾아내는 알고리즘을 생각합니다. O (N^2)

enter image description here

Answer 1

난 (N은 2 ^) O의 알고리즘을 생각한다. 먼저 우리는 가정 라인 y=2에 포인트

1. x -coordinates 비트의 유한 수에 의해 표현 될 수있다.
2. 이 x 좌표는 처음에 x으로 정렬됩니다. 그렇지 않다면 먼저 정렬하는 것은 O (nlog (n))
3. 입니다. 교차 선의 정의는 한정된 수의 비트로 점을 나타내는 정밀도와 관련하여 만들어집니다.
   1. y=2는 라인에 인접한 지점 간의 최소 거리를 찾아 다음과 같이

지금, 해시 함수를 구성. x - 좌표가 정렬되었으므로 O (n)입니다. 이 최소 거리 d이라고 부릅니다.
4. 해시 함수는 floor (2 * x/d)입니다. 이 해시가 y=2의 각 지점을 고유 한 저장소로 매핑한다는 것은 분명합니다. 이 연산 또한 O (n)입니다. 그런 다음

는, 다음을 수행하십시오 라인 y=0 및 y=1의 점의 각 쌍에 대한

1. , y=2에서의 교차를 계산한다. 이것은 O (n^2)입니다.
2. y=2에있는 각 교차점에 대해 y=2 줄에 점이 있는지 확인하기 위해 해시 테이블을 찾습니다. 있을 경우, 동일한 점인지 (기계의 정밀도 내에서), 그렇다면 교차 선이 있는지 확인하십시오. 그렇지 않으면 존재하지 않습니다. 해시 조회가 O (1)이므로 O (n^2)입니다.

따라서 알고리즘은 O (n^2)입니다. 코드는없고 아이디어 만 있습니다.