문제 링크
- http://icpc.me/10058
문제 출처
- 2014 ACM-ICPC World Final I번
사용 알고리즘
- 호프크로프트-카프 알고리즘
풀이
지름이 D인 원 내부에 있는 모든 점들은 모두 거리가 D 이하입니다.
지름의 양 끝에 있는 점을 중심(p, q)으로 하고, 반지름이 D인 원을 그려봅시다.
() 모양의 공간이 나옵니다. p와 D 이하로 떨어져있으면서 q와도 D 이하로 떨어져있는 점은 모두 () 안에 들어갑니다.
초록색 선을 기준으로, () 공간에 있으면서 초록색 선 위쪽에 있는 점들을 모두 D 이하로 떨어져있고 초록색 선 아래쪽도 마찬가지입니다.
그리고 지름이 D인 검은색 원 내부에 있는 점들도 모두 D 이하로 떨어져있습니다.
() 공간 안에 있으면서 검은색 원 외부에 있는 점들은 거리가 D 이하일 수도, D 초과일 수도 있습니다. 이 점들을 잘 처리해봅시다.
() 공간 안에 있으면서 검은색 원 외부에 있는 점들 중에서 서로 거리가 D 초과인 점들을 간선으로 이어줍시다. 이런 방식으로 그래프를 만들면 이분 그래프가 만들어지게 됩니다.
문제에서 최대 개수를 구하라고 했기 때문에, 거리가 D 초과인 점들을 가능한 가장 적게 제거해야합니다. 이 것은 최소 정점 덮개를 구하는 것으로 해결할 수 있습니다.
그러므로, 거리가 D 이하인 두 점 p, q에 대해 위에서 언급한 대로 그래프를 만들어주고 최소 정점 덮개를 제거해주는 방식으로 정답을 구할 수 있습니다.
시간 제한이 애매하기 때문에 호프크로프트-카프 알고리즘을 이용해 최소 정점 덮개를 구해주면 됩니다.