점과직선2 [기하] 스윕 라인 알고리즘(교차점, 가까운 점, 볼록껍질) | 모르면 절대 못 품 먼저 2차원 거리 측정 함수로 맨해튼거리(택시거리), 유클리드 거리 두 가지가 있다는 것을 알아두자. 교차점의 개수 세기선분이 N개 있을 때, 교차점의 개수를 세는 문제이다. 이때 각각의 선분은 수평 선분이거나 수직 선분이다. O(N^2)으로 쉽게 풀 수 있지만 스윕 라인 알고리즘과 구간 질의 자료 구조를 사용하면 O(NlogN) 시간에 풀 수 있다. 선분이 시작하는 점과 끝나는 점을 가지고 이벤트 처리하는 것이라고 생각하면 된다. 가장 가까운 점 쌍 찾기점 N개가 있을 때 유클리드 거리가 최소인 두 점을 찾는 문제이다. 이 문제도 스윕 라인 알고리즘으로 O(NlogN) 시간에 해결할 수 있다. 점들을 왼쪽에서 오른쪽 순서로 살펴보면서 d라는 값을 관리해 나간다.d는 현재까지 구한 두 점 사이의 최소 거.. 2023. 6. 2. [기하] 벡터와 외적의 활용 외적 기하문제에서 요긴하게 사용되는 외적을 이용해 알고리즘을 공부하자. 외적 배운 지 까마득 하지만.....🤣 우선 두 벡터의 외적 값 자체의 해석을 알아보자. 1. a x b > 0 : b는 왼쪽으로 회전한다. 2. a x b = 0 : b는 회전하지 않는다 또는 180도 회전한다 (a와 b가 평행하다.) 3. a x b < 0 : b는 오른쪽으로 회전한다. 점의 위치 판별하기 외적을 이용하면 어떤 점이 직선의 왼쪽 혹은 오른쪽 중 어느 곳에 있는지를 판별할 수 있다. 직선이 두 점 a, b를 지난다고 가정하자. 이때 방향이 a, b를 향하고 있고, 주어진 점은 p라고 하자. (p - a) X (p - b)를 구하면 p의 위치를 알 수 있다. 외적이 양수라면 p가 선분 왼쪽에 있는 것이고, 외적이 음수.. 2023. 5. 31. 이전 1 다음
