일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- IOI 2013
- boj
- 14179
- Z 알고리즘
- ICPC 연습
- DP
- 2794
- Manacher 알고리즘
- BAPC
- Manacher's algorithm
- 백준 온라인 저지
- codeforces
- 그래프
- 기하
- Implementation
- JOI 2018
- POI Solution
- 구현
- acmicpc.net
- Divide and conquer optimization
- 볼록 껍질
- convex hull
- 기하 알고리즘
- 컨벡스 헐
- JOI
- 코드포스
- 세그먼트 트리
- BAPC 2018
- 8192
- Z algorithm
- Today
- Total
프로그래밍 연습장
좌표평면에서 가장 먼 점 찾기 본문
아마 KOI 2016 먼 별 문제로 많은 사람이 알게 된 가장 먼 점 찾기 알고리즘이다.
문제: https://www.acmicpc.net/problem/10254
요약하자면, 2차원 평면상의 점이 N(2≤N≤100,000)개 있을 때, 유클리드 거리가 가장 먼 두 점을 찾으라는 것이다. 이 문제에서 첫 번째로 생각할 수 있는 것은 간단하다.
1. 가장 먼 두 점은 컨벡스 헐 위에 있다.
증명. 그 두 점 A, B 중 하나인 A가 컨벡스 헐 위에 없다고 하자. 그러면 다른 컨벡스 헐 위의 세 점이 있어, 그 세 점으로 이루는 삼각형 안에 A가 들어가게 된다(삼각분할). 그 세 점 모두 B와의 거리가 A보다 작다면 모순이므로, A, B는 가장 먼 점이 아니게 된다.
이제, 컨벡스 헐의 점들을 순서대로 돌면서 가장 먼 점을 찾는 방법을 생각할 수 있다! 두 이터레이터 i, j를 서로 반대편에 있게 한 바퀴 돌리면서 가장 먼 점을 찾아나가고 싶다. 현혹되기 쉬운 반례가 있는 한 방법은, i와 j의 거리가 극대가 될 때까지 j를 이동하는 것이다. 나도 이 방법을 예전에 사용했었고, 오답을 받았다. 증명 가능한 방법은 다음과 같다.
2. 가장 먼 두 점은, 어떤 기울기에 대해 양 끝의 두 점이다.
증명. 특히, 두 점을 잇는 직선에 수직한 기울기에 대해 양 끝이 아니라고 하면, 실제 양 끝 점이 더 멀게 된다.
가능한 기울기들 중에서, 컨벡스 헐의 각 변과 수직한 기울기들에 대해서만 모두 고려해보면 된다. 그렇지 않고 가장 먼 점이 있다고 해도, 그 점은 반대편에서 무조건 고려되기 마련이다. 반대편에서 기울기가 같은(아니면 기울기가 작은 것들 중에 가장 큰) 변을 찾고, 그 변의 양끝 점과의 거리를 고려하면 된다. 이는 변의 벡터를 생각하고, 그 벡터의 외적을 생각하면 된다. 두 벡터의 외적은 다음과 같이 정의된다.
$a \times b = a_x b_y - b_x a_y $
외적이 양수이면 두 벡터가 이루는 각도가 0도 초과 180도 미만이고, 음수이면 -180도 초과 0도 미만이다. ${A}_{i} {A}_{i+1} \times {A}_{j} {A}_{j+1} $가 0 이하가 될 때까지 j를 증가시키고, (i, j)와 (i, j+1) 두 가지 후보( (i, j+1)을 고려하는 이유는, 두 벡터가 평행할 때를 대비해서이다.)들을 계속 고려해주면서 i, j를 앞으로 나아가면 된다. 대략 다음과 같은 코드가 나오게 된다. vect(x)는 ${A}_{x} {A}_{x+1}$의 벡터를 pair로 리턴해주고, point(x)는 컨벡스 헐의 크기가 n일 때 x%n번째 점을 리턴해주는 함수이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 | lint ans = 0; int a = 0, b = 0; for (int i=0, j=1; i<n; i++) { while (cross(vect(i), vect(j)) > 0) j++; for (int k=j; k<j+2; k++) { lint d = dist(point(i), point(k)); if (d > ans) { ans = d; a = i; b = k; } } } | cs |
'알고리즘' 카테고리의 다른 글
Manacher의 알고리즘과 Z 알고리즘 (0) | 2018.02.27 |
---|---|
그래프의 간선 리스트 표현 (2) | 2017.12.06 |
Heavy Light Decomposition의 구현 (0) | 2017.12.03 |
배열을 이용한 Persistent Segment Tree의 구현 (0) | 2017.10.08 |
Graham Scan (0) | 2017.08.19 |