7890 - 가까운 점 찾기

https://www.acmicpc.net/problem/7890

7890번: 가까운 점 찾기

델로네 삼각분할을 이용하여, 한 점이 이루고 있는 선분 중 가장 작은 값이 정답이 되겠다.

Incremental Delauncy Triangulation 은, 나도 어떻게 구현 해야 할 지 모르겠다.
어떤 삼각형에 속하는지 알아내야 하는데, 난 잘 모르겠다. 이것도 스위핑으로 하면 될텐데…

다른 방식으로 보로노이 다이어그램을 이용한다.
보로노이 다이어 그램과 삼각분할은 듀얼 그래프 관계기 때문에, 보로노이 다이어 그램의 맞닿는 면을 서로 이어주면 삼각분할 그래프가 완성된다.

보로노이 다이어 그램을 구하는 알고리즘으로는 Fortune’s Algorithm을 이용하면 된다.

검색했을 때, 참고 할 수 있는 자료가 너무 적다. 나도 공부 할 때는 자료찾고 이해 안가서, 다른 더 쉬운 자료 찾아보고 계속했는데..

결국은 그림을 보고 이해했다.

포츈 알고리즘에서 비취 라인(Beach line) 이니 뭐니 많은 소리가 있다.

이것을 구현하는게 이 문제의 핵심이라고 할 수 있다.

해야 할 것은 크게 몇가지 없다.

일단 beach line은 어떻게 관리할 것이냐면, 그냥 이루고 있는 점들만 관리 할 것이다.

이때, 점들의 추가와 삭제를 실시간으로 해야함으로, BBST를 하나 익히고 있어야 한다.

세그먼트 쿼리를 응용하면 필요없긴 하다.

1. x축을 기준으로 정렬한다.

점을 순서대로 보면서 넣을 것이다.
Line이 다음 점의 x축 으로 움직일 때,
Beach Line의 변화를 모두 적용한뒤, 점을 집어넣는다.

집어 넣기전, 그 x축 까지 이동하며 생긴 event들, beach line의 변화를 적용한다.  그후 넣는다. 이때, 변화는 연쇄적으로 일어나서 여러 개의 점이 갑자기 사라질 수 있다.

어느 x축 시점에 각 점을 초점으로 하는 포물선이 완전히 사라지는지 계산한다.

이것을 우선순위에 넣고 관리한다.

이때는 Circle Event 라고 뭐 정해놓은게 있는 것 같은데, 그냥 세 점을 접하는 원의 중심축이 포물선에 닿는 x축 시점을 구하는 것이다. 그 시점이 포물선이 사라지는 시점과 동일하다. 이것을 잘 구현하는것이다.


일종의 dp라고 생각하면 된다.

Sweeping line을 기준으로, 한점을 집어넣기전 이미넣은 점들을 최적화 시켜, 가장 가까운 점을 빠른시간안에 찾는 것이다.

아직 문제 안풀긴 했는데, 휴가 나오면 바로 풀고 글도 새롭게 다시 쓰겠다.