BOJ 26108(Linear Regression) 풀이

이미지를 누르면 문제로 이동합니다

 

문제를 풀기에 앞서, 문제에 대한 설명 하겠다.

 

이 문제는 n과 k가 주어지고 이후 n 줄에 걸쳐 점의 좌표가 주어진다.

이때 n개중 k개를 제거해 n-k 개의 점에 대해 직선 y=ax+b에 대해 y좌표 차이가 최소가 되게 하는 거리를 구하는 문제다.

즉 n-k개의 점을 고르고 다양한 y=ax+b를 그려보면서 거리 차이가 최소가 되게 하는 y=ax+b를 찾고, 그때의 거리를 구하라는 문제다.

  

위 그림은 예제를 좌표평면에 나타낸 것이다. 

4개의 예제 중 k = 0 일 때를 알아보자.

k = 0 은 모든 점에 대해 거리가 가장 가까운 점을 찾는 것이다.

이때 답은 그림에서 나타난 두 직선의 중앙에 있는 직선이 된다.

 

그럼 이제 문제를 해결해 보자.

문제를 해결하기 위해선 크게 2가지를 해결해야 한다.

 

1. y = ax+b 가 무엇인가

2. n-k 개를 어떻게 뽑을 것인가

 

1번부터 해결해 보자.

우리는 이미 n-k 개의 점이 무엇인지를 알고 있다고 가정하자.

이 점들을 알고 있을 때 y = ax+b 를 어떻게 찾을 수 있을까?

 

우리가 구해야 되는 거리를 d라고 가정하자.

이 말은 y = ax+b에서 떨어진 가장 먼 점간의 거리가 d라는 소리다.

이 그림에서 파란색 원이 우리가 선택한 n-k개의 점 중 거리가 d인 점들이라고 하자.

이때 파란색 원은 위 그림같이 2가지의 형태로 나타날 수 있다.

 

1. y = ax + b에서 위로 d만큼 거리

2. y = ax + b에서 아래로 d 만큼 거리

 

y = ax + b에 대해 위와 아래로 d만큼 떨어진 점들의 집합을 나타내면 y = ax + b'와 y = ax + b'' 로 나타낼 수 있다.

 

이 그림을 보면 알 수 있는 사실이 하나 있는데, 그건 바로 거리 d는 y = ax + b'와 y = ax + b'' 의 거리의 절반으로 구할 수 있다는 것이다.

어찌 보면 당연한 것인데, y = ax + b에 대해 한쪽으로만 d 거리만 큼 떨어져 있다면 y = ax + b를 위쪽으로 이동함으로써 거리를 d/2로 줄일 수 있을 것이다. 즉 특정 기울기의 직선에 대해 위아래로 가장 멀리 떨어져 있는 두 점을 알아낼 수 있다면 우리가 원하는 d를 구해낼 수 있을 것이다.

 

이제 문제는 기울기 a를 어떻게 찾는가로 바뀌었다. 

 

우리는 방금 전 가장 멀리 떨어진 두 점간의 y좌표 차이를 안다면 답을 구해낼 수 있음을 알아냈다.

근데 y좌표 차이는 두 점을 지나는 직선사이의 거리에 임의의 삼각비 값을 곱하면 구해낼 수 있다.

(중고등 수학이나 물리의 역학을 공부하다 보면 자주 접할 수 있다)

즉 직선의 기울기를 활용한다면 두 점 사이 거리만으로 d를 구해낼 수 있다는 의미다.

이를 식으로 유도해 보자.

최대한 한 페이지로 정리했다. 그리고 잘 보면 마지막 부분을 제외하면 딱히 필요한 부분이 아니지만 다 작성한 이후에 깨달아서 그냥 남겨뒀다 ㅋㅋ....

 

두 직선 사이의 거리를 k라고 하고 직선의 기울기를 tanθ라고 해보자.

위 사진에 작성된 거처럼 tanθ 를 cosθ 로 나타내고, 2d와 k와의 관계에 대입해 주면 

\begin{equation} 2d = k\sqrt{a^2+1} \end{equation}

로 나타내줄 수 있다.

그리고 k는 두 직선 사이 거리 공식인 

\begin{equation} \frac{|c' - c''| }{\sqrt{a^2+b^2}} \end{equation}

를 이용해 주면 

\begin{equation} \frac{|b' - b''| }{\sqrt{a^2+1}} \end{equation}

로 정리할 수 있고, 앞서 구한 식을 바탕으로

\begin{equation} 2d = |b'-b''| \end{equation}

를 구해낼 수 있다.

이후 y = ax + b를 점에 대한 식으로 변환해 주면 b'와 b''를 나타낼 수 있게 되고, 최종적으로 이를 정리해 주면

\begin{equation} 2d = |a(C-A) - (D-B)| \end{equation}

를 구해낼 수 있다.

(정리하면서 안 사실이지만 2d = |b' - b''|  를 구하기 위해 cosθ 써서 요란하게 구해줬지만 사실 직선을 그려보면 2d는 y 절편사이 거리랑 같다는 걸 구할 수 있다 ㅋㅋ.... 이걸 다 작성해 놓고 알았다...) 

 

다시 돌아와서, 우린 이제 두 점과 기울기를 알면 d를 구해낼 수 있다.

그리고 여러 번의 테스트를 해본 결과, 한 점 A에 대해 A에서 가장 먼 점을 B라고 두고 A와 B를 지나는 직선의 기울기가 우리가 구하고자 하는 d를 만들어 낼 수 있는 기울기 중 하나가 되는 것을 알아내었다.

(이에 대해 수학적 증명을 해보고자 하였지만, 증명에 실패하여 실제로 AC를 받은 풀이를 설명하겠다.)

   

이제 어떤 점 사이 거리가 가장 먼지 찾아줘야 하는데, 이때 n^2를 해버린다면 당연하게도 시간초과가 발생할 것이다. 이때 우리는 로테이팅 캘리퍼스(Rotating Callipers)를 이용할 것이다.

 

로테이팅 캘리퍼스는 좌표평면에 놓인 점들 중 가장 먼 점사이 거리를 구할 때 사용하는 알고리즘이다. 컨벡스 헐로 볼록 껍질을 만들고, 볼록껍질을 회전하면서 가장 먼 점을 구해주는 방식이다.

시간 복잡도는 O(nlogn)으로 볼록껍질을 만드는데 O(nlogn), 로테이팅 캘리퍼스를 진행하는데 O(n)이 소요된다.

 

자세한 건 아래 링크에 작성되어 있는 로테이팅 캘리퍼스를 참고하길 바란다. (로테이팅 캘리퍼스를 공부할 때 참고한 자료이다.)

https://stonejjun.tistory.com/42

Geometry (4) - 로테이팅 캘리퍼스

 

로테이팅 캘리퍼스는 투포인터 형식으로 두 점을 회전시키면서 A에 대해 가장 먼 점을 찾아주는 방식이다. 이때 무조건 가장 긴 선분이 될 수 없는 점들을 탐색에서 제외해 줄 수 있기 때문에 사실상 모든 점을 탐색하는 것과 동치로 볼 수 있다.

 

점 A에 대해 가장 먼 점 B를 알았으니, A와 B를 지나는 직선의 기울기를 알아낼 수 있고, 점 A는 n-k개의 점이 회전하면서 차례로 선택되기 때문에 모든 점에 대해 가장 긴 거리를 구할 수 있게 된다.

 

이제 각 거리에 기울기에 대해 가장 멀리 떨어져 있는 점을 찾아주면 된다.

이는 이분탐색과 ccw를 이용한다면 찾을 수 있다.

 

우리는 볼록껍질 위 두 점 A와 B를 알고 있다. 이때 A와 B는 모두 볼록 껍질 위의 점이니 A와 B를 지나는 직선에 대해 왼쪽과 오른쪽에 있는 점들은 모두 특정 인덱스부터 연속적인 인덱스를 가지고 있음을 알 수 있다.

예시를 들어 설명해 보겠다.

직선 AB에 대해 가장 먼 점을 찾기 위해 이분탐색을 진행할 것이다.

이때 외적을 이용해 왼쪽으로 left를 업데이트할지, right를 업데이트를 결정할 것이다.

벡터의 외적은 아래 사진처럼 두 벡터가 이루는 평행사변형의 넓이다.

 평행사변형의 넓이를 반으로 나누면 삼각형의 넓이가 되기 때문에 외적의 크기는 삼각형의 크기에 비례한다고 볼 수 있다.

이제 문제를 해결해 보자.

점 i에 대해 외적의 넓이를 S(i)라고 정의하자.

위 예시에서 가장 멀리 떨어진 점은 i + 4이다.

즉 S(i+4) 가장 클 것이고, 좌우로 넓이가 작아지게 될 것이다.

이때 S(mid) <= S(mid+1)이라면 mid 보다 mid + 1 이 더 멀리 떨어져 있는 점이 될 것이다. 이러한 비교를 바탕으로 이분탐색을 진행하면 가장 멀리 떨어져 있는 점을 찾을 수 있게 된다.

 

이 과정을 양쪽에 대해 구해주면, 가장 멀리 떨어진 두 점을 구할 수 있게 되고 기울기와 이 점들을 활용해 거리를 계산하면 

최종적으로 n-k 개의 점에서 가장 작은 d를 구할 수 있게 된다.

 

---

 

이제 n-k 개의 점을 어떻게 구할 것인지에 대해 생각해 보자.

우리가 어떤 점들을 좌표평면에 나타내고, n-k 개를 뽑아야 된다면 어떻게 뽑을까?

일단 인접한 n-k 개의 점들로 뽑을 것이다.

이건 자명한 건데 굳이 내부 점을 선택하지 않고 밖에 점을 골라 거리를 늘릴 이유가 없다.

 

즉 우리는 연속되는 점 n-k개를 고르기 때문에 가짓수는 k+1 개가 되기 때문에 단순히 슬라이딩 윈도우로 탐색하면 되는 거 아닌가라고 생각할 수 있지만 여기서 문제가 하나 있다.

 

바로 누가 가장 먼저 나오는가 이다.

 

정렬이 x좌표를 기준으로 한다면, x가 작은 순으로 점들이 뽑히게 될 것이다.

근데? 만약 정렬이 임의의 직선에 대해 정렬을 한다면 n-k 개를 뽑는 경우가 달라질 수 있다.

예시를 통해 알아보자.

이 예시는 n = 8, k = 4 일때를 나타낸 것이다.

 

이 상황에서 x좌표를 기준으로 n- k = 4개를 뽑아보면 파란색 사각형안에 있는 점들이 뽑히게 될 것이다.

근데 노란색 직선을 기준으로 정렬을 하면 파란색 사각형 안에 있는 점들 중 맨 아래에 있는 점을 빼고 오른쪽에 있는 점을 하나 선택하게 된다. 이처럼 직선의 기울기에 따라 나오는 점들의 순서가 달라질 수 있다.

 

이에 관해서는 불도저 트릭(Bulldozer Trick)에서 확인해 볼 수 있다.

https://justicehui.github.io/hard-algorithm/2022/03/30/rotate-sweep-line/

Rotating Sweep Line Technique (Bulldozer Trick)

 

위 불도저 알고리즘에선 O(n^2)을 통해 순서를 찾지만 우리는 n = 50000까지 들어오기 때문에 O(n^2) 은 할 수 없다.

 

그럼 어떻게 해야 할까?

 

본인은 이를 해결하기 위해 아래 유튜브에서 아이디어를 얻었다.

https://www.youtube.com/watch?v=M64HUIJFTZM

 

과거 IMO에 나왔던 문제에 대한 설명인데, 여기서 주목해야 될 점은 임의의 점에서 시작해 직선을 반시계 혹은 시계방향으로 회전하면서 점을 만날 때마다 축을 변경해 주면 직선에 의해 나눠지는 반평면에 존재하는 점의 개수가 항상 일정하다는 것이다.

 

저 아이디어를 알아내면 맨 처음에 x좌표를 기준으로 정렬하고 첫 번째부터 k+1 번째까지 점에서 시작해서 회전하면 한쪽에 남아있는 개수를 i (1 ~ k+1)로 남길 수 있음을 알게 된다.

그리고 이를 반대쪽에서 적용해 k번 반복하면서 x좌표 기준 i번째 점, n-k+i 번째점에서 시작해 선분을 회전시키면서 두 직선 사이에 들어오는 점들만을 따져주면 된다는 사실을 발견할 수 있다.

 

본인도 실제로 이렇게 해서 코드를 구현하였는데, QOJ 기준 84개의 테스트 케이스 중 70개가량을 맞췄지만 이후 테스트 케이스에선 시간초과를 받았다. 80%짜리 방법론이라는 것이다.

 

그럼 여기서 어떻게 개선해야 될까?

 

우린 여기서 맨 처음으로 돌아가 왜 n-k 인지를 고려해 볼 필요가 있다.

n은 5만까지, k는 n/2과 300 중 최솟값으로 n이 600 이상일 때부턴 300으로 생각해 주면 된다.

즉 양끝 몇 개만 선택 혹은 선택하지 않음의 대상이 되고, 중앙에 있는 일부의 점들은 항상 선택이 된다는 것이다.

n-k 개를 한쪽에 치우쳐 고르게 된다면 반대쪽에는 먼저 나오는 순으로 최대 k개가 선택되지 않을 것이다.

이를 고려하면 양끝에서 k 개씩 빼고 남은 n-2k 개의 점들은 항상 포함됨을 알 수 있다.

 

이제 문제는 2k 개에서 k개를 고르는 문제로 바뀌게 된다.

 

k개를 고르는 방법론을 설명하기 전에, 어떤 경우가 정답을 보장하는 구간인지를 찾는 방법에 대해 설명하겠다.

우리는 앞서 설명한 방법들을 통해 n-k 개를 line rotation을 통해 얼추 추려낼 수 있음을 알아내었다.

하지만 이러한 n-k 개중 어떤 게 우리에게 필요한 방법인지 모르고, 1번 방법에서 rotation calipers를 이용한 방법은 O(nlogn) 이기 때문에 회전하는 내내 탐색을 해주기에는 부담이 있다.

 

그래서 어떤 조합을 선택해야 되는지 알아내기 위해 시뮬레이션을 구현했고, 다양한 예제를 테스트해 보면서 방법을 알아내었다.

(이 방법도 증명을 시도하였으나 실패하여 AC 가 나온 방법에 대해 설명하겠다)

 

https://www.youtube.com/watch?v=Gcct_fC3VFQ

 

이 영상은 실제로 구현한 시뮬을 문제에서 제공된 예제에 대해 테스트를 해본 것이다.

Linear Regression 이 우리가 구하고자 하는 값이다.

영상을 보면 두 선분의 y좌표차가 가장 작을 때 우리가 구하고자 하는 값이 나온다는 걸 알 수 있다.

그러니 우리는 회전을 하면서 두 직선의 차이가 가장 작을 때의 점들을 가지고 rotation calipers를 해주면 된다.

 

다시 돌아와서 k개를 고르는 방법에 대해 알아보자.

우리는 맨 처음에 두 직선사이 개수가 n-k 개가 되도록 k번 반복하면서 탐색을 해주었다.

2k 개가 남은 상황에서도 비슷하게 해 주면 되는데, 왼쪽 k개중 i개를 뽑는다면 오른쪽은 k개중 k-i 개를 뽑게 될 것이다.

그리고 여기서 뽑는 순위는 직선에서 가까운 순이 될 것이다.

 

여기서 우리는 k의 범위가 작다는 걸 한 번 더 다시 한번 생각해 볼 필요가 있다.

k가 최대 300이기 때문에 k번 반복을 추가해 줘도 시간복잡도는 크게 늘어나지 않는다.

그리고 우리는 양쪽에 k 개씩을 남기고 있으니 양쪽으로 k번씩 반복을 하면서 거리 순으로 정렬을 해준 뒤, 한쪽을 역순으로 해 더해주면 우리가 원하는 n-k개의 점사이 거리를 구할 수 있게 될 것이다.

 

정려 같은 경우, 벡터나 배열 담고 정렬을 해줘도 되지만 본인은 우선순위 큐를 활용하였다.

내림차순 우선순위 큐와 오름차순 우선순위 큐를 준비해서 한쪽은 오름 차순, 한쪽은 내림차순으로 k개를 추가해 줬다.

그리고 둘을 앞에서부터 뽑으면서 거리를 더해줬고, 기존에 보장된 점들의 거리를 계산해 n-k 개 점의 거리를 구해주었다.

 

이렇게 거리를 계산해 줬으면, 위 과정을 한 번 더 해주면서 최솟값이 다시 나왔을 때 점들을 뽑아주면 된다.

점을 뽑는 건 간단한데 방금 전 영상을 보면 회전을 하면서 만나는 점들은 각자의 상태가 swap 이 된다. 

그러니 축점이 바뀔 때마다 서로 상태를 swap 해주고, n-2k 개 점을 저장하고 업데이트해 나간다면 충분히 우리에게 필요한 점들을 알아낼 수 있다.

이 과정에 대해서는 깊게 설명하지 않겠다.

---

다음으로 알아본 건 회전하는 두 직선을 어떻게 회전시킬 것인지에 대해 알아보고자 한다.

직선이 회전하면서 만나는 점의 순서를 다 알고 있다고 가정하자.

왼쪽에서 k+1 번째 점, 오른쪽에서 k+1 점에서 시작해 직선을 회전하다 보면 왼쪽 직선과 오른쪽 직선 중 먼저 어느 점에 만나는 직선이 있을 것이다. 

이 점이 무엇인지 알아내기 위해선, ccw, 내적, 외적을 모두 활용해야 한다.

설명에 앞서, 풀이에서 사용하는 내적 외적 공식과 이를 변형한 식에 대해 다루겠다.

\begin{equation} A\cdot B = |A||B|cos\theta = A_xB_x+A_yB_y\\ A\times B = |A||B|sin\theta \hat{i} = A_xB_y - A_yB_x\\ \frac{|A\times B|}{A\cdot B} = tan \theta \end{equation}

위에 두줄은 외적 공식과 내적 공식을 나타낸 것이고, 맨 마지막 식은 외적과 내적을 이용해 tanθ 를 구해준 것이다.

이 과정을 통해 우리는 sinθ, cosθ, tanθ 을 모두 구해낼 수 있다.

이 삼각함수를 어떻게 이용할 수 있을까?

바로 사분면 결정 및 단조성을 활용한 각 크기 비교이다.

우리가 중고등학교 때 배우는 삼각함수에선 각 사분면마다 삼각함수의 부호의 조합이 다르다.

즉 이 부호의 조합에 따라 각의 크기가 몇 사분면에 해당하는지 알 수 있고, 이 사분면을 비교하면 누가 더 먼저 나오는지 알아낼 수 있다.

이때 sinθ, cosθ를 이용하면 사분면을 특정할 수 있는데, 우리는 여기서 양수인지 음수인지만을 체크하기 때문에 외적값, 내적값을 그대로 이용해서 사분면을 체크해 준다.

 

이러면 다른 사분면에서의 크기 비교를 할 수 있게 되고 같은 사분면일 때만 남게 되는데, 같은 사분면의 경우 tanθ 를 이용해 줄 것이다.

tanθ 를 그려보면 알 수 있지만 pi 구간에서 단조 증가의 형태를 보인다. 즉 각이 클수록 값이 커지기 때문에 같은 사분면만 있을 때 크기를 비교하는 데 사용할 수 있다.

 

이러한 방법을 통해 누가 더 각이 작은 지를 구할 수 있게 되고, 결과에 따라 왼쪽 직선 혹은 오른쪽 직선을 업데이트해주면 된다.

---

이제 전반적인 풀이 설명을 다했다.

2번 과정을 통해 최소 거리인 점들의 집합을 구해주고 rotation callipers를 활용해 정답을 구해주면 된다.

하지만 여기서 걸림돌은 위 영상들에서 나타나는 line rotation을 어떻게 구현할 것인가이다.

 

여기서부터는... 그냥 쌩 구현이다.

대신 구현을 위해 사전에 만들어야 될 게 있는데 바로 k+1개의 컨벡스 헐이다.

우리는 회전을 통해 한쪽에 k개의 점들이 있게 할 것이다. 즉 k+1 이후의 점들은 회전 과정에서 선택되지 않을 수도 있다는 것이다.

그리고 그 점들은 k+1 개의 컨벡스 헐을 만들어주고 나머지 점들을 하나의 그룹으로 몰아주면 해결할 수 있다.

(이 부분도 왜 k+1개의 컨벡스 헐을 구해줬지 기억이 나지 않아 AC 받은 방법에 대해 설명하겠다)

 

k+1 개의 컨벡스헐의 경우 O(knlogn)으로 나이브하게 구해줄 수도 있지만, Monotone Chain 기법을 활용한다면 O(nlogn + kn)으로 시간복잡도를 줄여줄 수 있다.

Monotone Chain는 x좌표를 기준으로 정렬을 하고, 아랫껍질, 윗껍질을 따로 구해주어 컨벡스 헐을 구해내는 방식이다.

 

https://m.blog.naver.com/gktgnjftm/221459483950

Convex Hull (Monotone Chain 기법)

이 블로그에서 쉽게 이해할 수 있다.

 

이제 k개(+1 생략)의 컨벡스 헐을 활용 해보자.

컨벡스헐의 특징은 점들을 시계 혹은 반시계 방향으로 정렬시킬 수 있다는 것이다.

 

일정한 상태로 정렬되어 있다는 것은 굉장히 좋은 조건임을 ps를 하다 보면 많이 느낄 수 있다.

이 문제에서도 이렇게 정렬된 방법을 이용해야지 문제를 해결할 수 있다.

 

앞선 내용을 되새겨보면 우리는 line rotation을 해줘야 되고, line rotation에서 가장 먼저 만나는 점이 무엇인지를 찾아줘야 한다.

이때 우리는 구한 k개의 컨벡스헐에 대해 탐색을 진행해 주면서 후보를 골라줄 것이다.

그리고 각 컨벡스헐에선 케이스 워크를 해줘야 한다.

총 6가지의 경우가 있다.

 

1. 컨벡스 헐과 직선이 만나는 점이 0개 일 때

2. 컨벡스 헐과 직선이 만나는 점이 1개 일 때

3. 컨벡스 헐과 직선이 만나는 점이 2개 이면서 컨벡스헐의 두 꼭짓점에서 만날 때

4. 컨벡스헐과 직선이 만나는 점이 2개 이면서 컨벡스헐의 한 꼭짓점과 한 변에서 만날 때

5. 컨벡스헐과 직선이 만나는 점이 2개 이면서 컨벡스헐의 두 변에서 만나고 축점이 컨벡스헐 외부에 있을 때

6. 컨벡스헐과 직선이 만나는 점이 2개 이면서 컨벡스헐의 두 변에서 만나고 축점이 컨벡스헐 외부에 있을 때

(진짜 케이스 워크는 사회 악이다.)

 

이에 대해서 예시를 들어 설명하겠다.

 

---

 

1. 컨벡스 헐과 직선이 만나는 점이 0개 일 때

1번 예시 그림

 

1번은 위 그림처럼 컨벡스헐에 해당되는 점이 시계 혹은 반시계 방향으로 정렬되어 있고, 그 컨벡스헐 밖에 직선이 있는 경우다.

빨간색 점은 회전 축점이다.

 

위 상황에서 다음으로 만나게 될 점은 1번 점이 될 것이다.

이 경우 우리는 축점과 컨벡스헐 사이 접점을 찾아줘야 한다. 

접점을 찾는 이유는 외부에 있는 직선이 회전하면서 컨벡스헐과 만나려면 어떠한 한 점에서 처음 만나게 되기 때문에 접점이 다음 점의 후보가 되는 것이다.

그리고 접선 개수만큼 접점이 생기기 때문에 위 상황에서 생기는 두 접점을 모두 후보군으로 올려 가장 가까운 점을 찾아주면 된다.

여러 후보군에서 가장 먼저 접하게 되는 점을 찾는 방법의 경우, ccw를 잘 활용하면 구해낼 수 있다.

이 상황을 예시로 설명을 해보겠다.

축점은 빨간색 점, 현재까지 가장 가까운 점으로 선택되어 있는 점은 파란색 점, 현재 후보군으로 올라온 점을 초록색, 보라색 점이라고 하자.

위 상황에서 우리는 보라색 점은 버리고, 초록색 점을 선택해야 된다는 것을 알 수 있다.

그럼 초록색 점과 보라색 점의 차이는 뭘까?

 

그건 바로 빨간색 점, 파란색 점에 대해 ccw의 부호가 다르다는 것이다.

보라색 점은 ccw 크기가 음수(시계 방향), 초록색 점은 양수(반시계 방향) 이 될 것이다.

여기서 반시계 방향에 점이 있다는 건 파란색 점보다 초록색 점이 더 먼저 만날 수 있다는 것이다. 

그러므로 반시계 방향이 나올 때마다 가장 가까운 점을 업데이트해 나가면, 후보군 사이에서 우리가 원하는 점을 찾아낼 수 있다.

 

다시 돌아와 접점은 어떻게 찾을 수 있을까?

https://leo630.tistory.com/m/146

이분 탐색을 이용한 볼록 다각형의 접선 찾기

그 해답은 위 블로그에서 찾을 수 있다.

제목에서부터 우리가 원하는 정보를 담고 있음을 알 수 있다.

그러므로 굳이 구체적인 설명은 하지 않고, 위 블로그에 나와있는 방식 그대로 구현을 해주면 된다.

(본인의 경우, 컨스헐이 반시계 방향으로 정렬이 되어 있어 조오오금 더 복잡하게 작업을 진행하였다)

 

이렇게 1번 케이스에 대한 방법을 찾았다. 나머지 5개도 차례로 알아보자.

---

2. 컨벡스 헐과 직선이 만나는 점이 1개 일 때

 

2번 예시 그림

 

2번의 경우, 위와 같은 경우이다.

이때 축점이 컨벡스헐에 포함되지 않을 수도 있지 않느냐라고 할 수 있는데, 

해당 경우는 이전 스텝에서 이미 1번점에 만나게 된 게 되므로, 현재 스텝에선 1번을 지나 내부를 관통하고 있는 상태가 된다.

그러므로 현재 상황과는 맞지 않기 때문에 만나는 점이 1개일 때는 컨벡스 헐 위의 점일 때만 된다.

 

이 경우는 간단하게 구할 수 있는데, 컨벡스 헐을 저장할 때, 해당 번호의 점이 몇 번째 인덱스인지 저장해 두고 이 상황에서 그 값을 불러와 인덱스 + 1을 해주면 된다. 시계방향으로 돌기 때문에 당연하게도 1번점 다음은 2번이 될 것이다.

 

---

3. 컨벡스 헐과 직선이 만나는 점이 2개 이면서 컨벡스헐의 두 꼭짓점에서 만날 때

 

3번 예시 그림

 

3번은 다음과 같은 경우이다. 여기서도 2번과 비슷한 맥락으로 항상 컨벡스헐 위에 축점이 존재한다.

이때도 쉽게 다음 점을 구해낼 수 있다.

 

위 상황에서 3번점은 현재 축점이 될 것이고, 2번 점은 바로 전 축점이 될 것이다.

(이 부분은 회전에 대해 생각해 보면 자명하다)

그러므로 우린 두 점이 무엇인지 알고 있기 때문에 두 점에 대해 다음 혹은 전 인덱스를 모두 후보로 올려 처리해 주면 끝이다.

---

4. 컨벡스헐과 직선이 만나는 점이 2개 이면서 컨벡스헐의 한 꼭짓점과 한 변에서 만날 때

 

4번 예시 그림

 

4번은 다음과 같은 경우다. 이때도 맞찬가지로 축점이 항상 컨벡스 헐 위에 있음이 보장된다.

이때는 조금 복잡해지는다. 이를 해결하기 위해 임의의 직선에 대해 컨벡스헐에 있는 점들의 상태를 나타내보자.

 

어떤 직선에 대해 왼쪽을 L, 오른쪽을 R이라고 하자.

왼쪽 오른쪽 정의는 i-1 축점에서 i 축점으로 나아가는 벡터를 기준으로 하겠다.

이때 경우는 총 6가지가 나오게 된다.

 

A. LLLLLLLLL

B. RRRRRRR

C. LLLLLRRR

D. RRRRLLLL

E. LLLRRLLL

F. RRRLLRRR

 

A와 B는 하나도 만나지 않을 때와 동치다.

우리가 고려해야 될 건 C부터 F다.

우리는 저 형태의 입력에서 L과 R의 분단점을 찾아야 된다. 분단점은 L에서 R로, 혹은 R에서 L로 바뀌는 지점으로

즉 우리가 구해야 하는 가장 가까운 점의 인덱스를 의미하게 된다.

 

C와 D의 경우는 간단하다. L 혹은 R이 반복되다가 다른 값이 나타나기 때문에 단순하게 이분탐색을 이용해 준다면 쉽게 구해낼 수 있다.

문제는 E와 F인데, E는 L, F는 R을 알아냈을 때 이 값이 왼쪽과 연결된 건지, 오른쪽과 연결된건지 알 방법이 없다.

이를 해결하기 위해선 추가 정보가 필요한데 이에 대해선 4번, 5번, 6번 케이스마다 추가 정보 및 해결방법에 대해 설명하겠다.

 

다시 돌아와서 4번의 경우, 위 E와 F의 문제는 쉽게 해결할 수 있다.

우리는 컨벡스 헐에서 좌우를 분단하는 하나의 점인 축점을 알고 있다.

즉 축점의 인덱스를 기준으로 좌우를 나누게 된다면 LLRR 혹은 RRLL 2개로 나눠짐을 보장할 수 있다.

LLRR과 RRLL의 상태를 알아내었으니, C와 D처럼 이분탐색을 통해 경계지점을 찾아주면 된다.

 

---

5. 컨벡스 헐과 직선이 만나는 점이 2개 이면서 컨벡스헐의 두 변에서 만나고 축점이 컨벡스헐 외부에 있을 때

 

5번 예시 그림

 

5번은 위와 같은 경우이다.

이때 E와 F의 상황은 상당히 골치가 아프다. 본인도 이를 해결하기 위해 많은 시간을 쏟았다.

우리가 해결해야 되는 것은 LLLRRRLLL 상황에서 두 L이 어느 쪽 L인지, RRRLLLRRR 상황에서 두 R이 어느쪽 R인지 알아내는 것이다.

 

이때 우리는 앞서 사용했던 접점을 다시 한 번 더 사용할 것이다.

위 그림을 회전시켜서 다시 한번 나타내보겠다.

다시 나타내보면 위와 같은 상태가 될 것이다.

여기서 주황색, 보라색 점은 접점, 파란색, 초록색 선은 접선이다.

 

이제 접점의 상태를 확인해 보자. 두 접점은 서로 다른 상태를 가질 것이다.

즉 하나가 L 이면 나머지는 R이 될 것이다.

우린 4번에서 하나의 점으로 두 구간을 나눠서 이분탐색을 했었는데, 여기서 접점의 상태를 알고 있으니 컨벡스헐의 첫 번째 점의 상태와 비교해서 상태가 다른 지점을 기준으로 반으로 나누면 된다.

 

위 그림에서 만약 첫번째 점이 주황색 쪽에 있다면 보라색 점으로 반을 나누고, 반대로 보라색 쪽에 있다면 주황색 점을 기준으로 반을 나눠 이분탐색을 진행해 주면 된다.

 

---

6. 컨벡스 헐과 직선이 만나는 점이 2개 이면서 컨벡스헐의 두 변에서 만나고 축점이 컨벡스헐 외부에 있을 때

 

드디어 마지막이다.

여기까지 읽고 있는 자신과 작성하고 있는 본인에게 다 왔다는 격려를 해주고 가자.

 

6번의 경우에는 ccw를 이용해 계산을 할 것이다.

위 그림처럼 현재 직선과 축점과 1번점을 이은 벡터를 만들어 주자.

우린 이 두 벡터를 이용해 영역을 나눠줄 것이다. 

이를 이해하기 위해선 좌표 평면에서 각 축에 대해 ccw가 어떻게 생기는지 알아볼 필요가 있다.

검은색 글씨는 사분면을 나타낸 것이고, 색깔 부호는 해당 색의 축에 대한 ccw의 부호를 의미한다.

여기서 볼 수 있는 점은 각 사분면마다 부호의 조합이 다르다는 것이다. 

즉 우리가 두 벡터의 상태를 알고 있다면, 우리가 알고자 하는 점이 무슨 사분면에 있는지 알아낼 수 있다.

 

다시 돌아와서 우리의 상황에 이걸 적용해 보자.

축점과 1번점을 연결한 벡터와 축점을 지나는 현재 상태의 직선, 두 벡터를 우린 알고 있다.

 

두 벡터에 의해 만들어지는 4개의 평면 중엔 왼쪽 L, 그리고 오른쪽 L  (LLLRRRLLL 상태라고 가정하자)

를 나타내는 평면이 존재할 것이다.

 

우리가 알아내야 하는 왼쪽 혹은 오른쪽 구간 중 어느 곳에 포함되는지 여부를 특정 평면에 속하는가를 통해 분리할 수 있게 되었다.

이쯤 왔으면 다들 알아챘겠지만 임의의 점이 L일 때 그게 왼쪽인지 오른쪽인지를 ccw를 통해 판별하고 그거에 맞춰 이분탐색을 줄여나가면 된다.

 

---

지금까지 6가지의 큰 케이스 워크와 그 사이에 껴있는 6 + @ 개의 케이스 워크를 고려해 총 12 + @ 개의 케이스 워크에 대해 알아봤다.

정말 케이스 워크는 거지 같다.

 

우리는 지금까지 컨벡스 헐 k개 만들기, 로테이션을 구현하는 방법, 로테이션 순서 결정 방법, 직선 사이 거리 계산 방법, 로테이션 캘리퍼스 활용 방법에 대해 알아봤다.

 

이 내용들을 방금 말한 순서대로 아주 아주 아주 아주 아주 아주 아주 아주 아주 아주 매우 잘 구현해 주면 문제를 풀 수 있게 된다.

(괜히 루비 1이 아니다....)

 

그럼 모두 파이팅!