ICPC 준비용으로 다이아 중하위 정도의 모르는 주제들을 공부하고 있다. 그러다 학교 알고리즘 수업 과제로 이 문제가 나왔던 것이 생각나서 한 번 짜 보기로 했다. 핸드라이팅 과제였기 때문에 짜둔 코드가 없어 애먹긴 했지만, 어찌저찌 이 문제를 풀고 나서 보니 마땅한 한국어 설명 글도 없고(아마), 몇몇 팀 팀노트에 코드가 있긴 하지만 이해가 힘들고 내가 푼 방법과 다른 것 같아 설명 목적으로 글을 작성하려 한다.
문제 요약
볼록 다각형 밖의 점 \(P\)에서 다각형으로 접선을 그었을 때 생기는 두 접선의 접점을 구하여라. 편의상 볼록 다각형의 세 꼭지점이 일직선을 이루지 않고, 점들이 반시계 방향으로 정렬되어 있다고 가정하자. 만약 접점이 두 개일 경우, \(P\)와 가까운 점을 접점으로 한다.
풀이 설명
접선을 그었을 때 도형이 접선의 왼쪽에 있는 경우를 upper, 오른쪽에 있는 경우를 lower라 하겠다. 또한 편의상 upper 접선의 접점을 \(A_u\), lower 접선의 접점을 \(A_l\)이라고 하자.
이 풀이에서 핵심적으로 사용하는 성질은 반직선 \( \bar{PA_{i}}\)에 대한 \(A_{i-1}\)과 \(A_{i+1}\)의 위치 관계이다.
\(A_u\)의 경우 \(A_{i-1}\)과 \(A_{i+1}\)이 반직선 왼쪽에 있으며, \(A_l\)의 경우 두 점이 반직선 오른쪽에 있다. 이러한 판별은 ccw를 이용해 할 수 있음이 알려져 있다.
접점이 아닌 점들의 경우 두 가지로 나눌 수 있는데, 반시계 방향 기준으로 \(A_u\) → \(A_l\)로 가는 경로에 있는 점들과 \(A_l\) → \(A_u\)로 가는 경로에 있는 점들로 나눌 수 있다. 전자의 경우에는 \(A_{i-1}\)이 반직선 오른쪽에, \(A_{i+1}\)이 반직선 왼쪽에 있으며, 후자의 경우에는 \(A_{i-1}\)이 반직선 왼쪽에, \(A_{i+1}\)이 반직선 오른쪽에 있다.
앞으로는 반직선 \(\bar{PA_{i}}\)에 대한 \(A_{i-1}\)과 \(A_{i+1}\)의 위치 관계를 편의상 \((L,R)\)과 같이 표현하도록 하겠다. 점들은 반시계 방향으로 정렬되어 있으므로, upper 접점 에서 시작해 lower를 지나 한 바퀴 도는 상황을 생각해 보면 위치 관계는 \((L,L)\) → \((R,L)\) → \((R,R)\) → \((L,R)\) 과 같이 변화한다는 것을 알 수 있다.
\(A_u\)를 찾는 것은 이러한 배열에서 \((L,L)\)을 찾는 것이고, \(A_l\)을 찾는 것은 이러한 배열에서 \((R,R)\)을 찾는 것이다. 접점이 여러 개인 경우는 우선 나중에 생각하도록 하자.
배열이 항상 저렇게 생겼다면 이분 탐색을 적용하기 수월하겠지만, 그렇지 않다. 시작점의 위치 관계는 어떤 상태일 수도 있기 때문에, \((L,R)\) → \((L,L)\) → \((R,L)\) → \((R,R)\) → \((L,R)\)과 같은 경우가 있을 수 있다. 이를 해결하기 위해서는 앞 \((L,R)\)과 뒤 \((L,R)\)을 구분해야 한다. 이를 위해서는 다음과 같은 성질이 이용된다.
Corollary: 볼록 다각형을 \(A_u\)와 \(A_l\)을 기준으로 두 부분으로 나누었을 때, 각 부분의 점들은 \(P\)를 기준으로 각도순으로 정렬되어 있다.
접점 자체가 방향이 바뀌는 점들이나 마찬가지이기 때문에 이는 항상 성립한다. 따라서 \((L,R)\) → \((L,L)\) → \((R,L)\) → \((R,R)\) → \((L,R)\)과 같은 경우에서 이분 탐색을 할 때 현재 보고 있는 점이 \((L,R)\)이라면 이 변을 가장 앞 변과의 ccw를 통해 가장 앞 부분에 속하는지 가장 뒤 부분에 속하는지 구분해줄 수 있다. 시작 점이 \((R,L)\)인 경우에도 비슷한 방법으로 이분 탐색을 시행해주면 된다.
이를 정리하면, 이분 탐색을 이용해 \(A_u = (L,L)\)을 찾는다고 할 때
1) 시작 점이 \((L,R)\) 또는 \((L,L)\)인 경우: \((L,R)\) → \((L,L)\) → \((R,L)\) → \((R,R)\) → \((L,R)\)
만약 현재 보고 있는 점이 앞이 R이거나 \((L,R)\)이면서 \(\bar{PA_0}\) 왼쪽에 있는 경우 \(r\)을 줄이고, 그렇지 않은 경우 \(l\)을 늘리면 된다. 시작 점이 \((L,L)\)인 경우에 모든 \((L,R)\)이 왼쪽에 있기 때문에 잘 동작한다.
2) 시작 점이 \((R,L)\) 또는 \((R,R)\)인 경우: \((R,L)\) → \((R,R)\) → \((L,R)\) → \((L,L)\) → \((R,L)\)
만약 현재 보고 있는 점이 \(R,L\)이면서 \(\bar{PA_0}\) 오른쪽에 있는 경우 \(r\)을 줄이고, 그렇지 않은 경우 \(l\)을 늘리면 된다. 역시 시작 점이 \((R,R)\)인 경우에도 잘 동작한다.
이제 접점이 2개인 경우를 생각해보자. upper 접점이 2개인 경우 \((L,L)\) 대신 \((L,0)\) → \((0,L)\)이 등장하고, lower 접점이 2개인 경우 \((R,R)\) 대신 \((R,0)\) → \((0,R)\)이 등장한다. 전자의 경우에서는 \((L,0)\)을, 후자의 경우에서는 \((0,R)\)을 접점으로 생각하고 싶다. 따라서, \(A_{i-1}\)과의 위치 관계를 따질 때에는 0을 R에 포함시키고, \(A_{i+1}\)과의 위치관계를 생각할 때에는 0을 L에 포함시키면 잘 정의된다.
이때까지 설명을 위해 위치 관계를 두 개 사용했지만, 사실 하나로도 충분하다. 여기서는 \(A_{i-1}\)과의 위치 관계만 사용한다고 생각하겠다. 앞에서 다룬 경우를 다시 살펴보자.
1) 시작 점이 \((L,R)\) 또는 \((L,L)\)인 경우
\(r\)을 줄이는 경우가 아니라 \(l\)을 늘리는 경우를 생각해보면, 현재 보고 있는 점이 앞이 \(L\)이면서 \(\bar{PA_0}\) 오른쪽에 있는 경우이다. 따라서 앞만 확인하고, 나머지 경우에 \(r\)을 줄이면 된다.
2) 시작 점이 \((R,L)\) 또는 \((R,R)\)인 경우
만약 현재 보고 있는 점이 \(R,L\)이면서 \(\bar{PA_0}\) 오른쪽에 있는 경우 \(r\)을 줄이는데, 자명하게 보고 있는 점의 앞이 \(R\)인지만 확인해도 된다. \((R,R)\)은 어차피 가장 왼쪽에 있어 두 번째 조건에 걸리지 않기 때문이다.
이를 구현해주면 \(A_u\)를 찾을 수 있다. \(A_l\)도 같은 방법으로 찾아줄 수 있는데, 정리해보면 그냥 \(A_u\)를 찾는 과정에서 모든 부등호를 뒤집어주면 된다.
코드
ll findut(pll p) //L,L 찾기
{
ll l=0,r=n-1,m,b,a;
while(l<r)
{
m=(l+r+1)/2;
b=(m-1+n)%n; a=(m+1)%n; //b->m->a
if(ccw(p,ar[0],ar[n-1])<=0) // 앞 R
{
if(ccw(p,ar[m],ar[b])<=0&&ccw(p,ar[m],ar[a])>=0&&ccw(p,ar[0],ar[m])<0)
r=m-1;
else l=m;
}
else
{
if(ccw(p,ar[m],ar[b])<=0||(ccw(p,ar[m],ar[b])>0&&ccw(p,ar[m],ar[a])<0&&ccw(p,ar[0],ar[m])>0))
r=m-1;
else l=m;
}
}
return l;
}
ll findlt(pll p)
{
ll l=0,r=n-1,m,b,a;
while(l<r)
{
m=(l+r+1)/2;
b=(m-1+n)%n; a=(m+1)%n; //b->m->a
if(ccw(p,ar[0],ar[n-1])>0) // 앞 L
{
if(ccw(p,ar[m],ar[b])>0&&ccw(p,ar[m],ar[a])<0&&ccw(p,ar[0],ar[m])>0)
r=m-1;
else l=m;
}
else
{
if(ccw(p,ar[m],ar[b])>0||(ccw(p,ar[m],ar[b])<=0&&ccw(p,ar[m],ar[a])>=0&&ccw(p,ar[0],ar[m])<0))
r=m-1;
else l=m;
}
}
return l;
}
원래 블로그에 코드를 잘 올리지 않지만, 특별히 올려보았다. 함수를 하나로 합칠 수 있을 것 같긴 한데 깔끔하게 될지는 잘 모르겠다.
질문과 지적 많이 부탁드립니다.