거미줄
시간 제한2초메모리 제한128 MB
convex 다각형의 꼭짓점과 원형 웅덩이가 주어질 때, 웅덩이를 피하면서 서로 교차하지 않는 대각선을 최대 몇 개까지 연결할 수 있는지 구합니다.
문제
동주는 자신의 논에 거대한 거미줄 모양의 예술 작품을 만들려고 한다.
N개의 기둥은 볼록 다각형의 꼭짓점이 되도록 놓여 있다. 동주는 두 기둥을 줄로 연결할 수 있지만, 다음 조건을 모두 지켜야 한다.
- 서로 이웃한 두 기둥은 줄로 연결할 수 없다.
- 어떤 두 줄도 서로 교차하면 안 된다. 줄이 같은 기둥에서 만나는 것은 허용된다.
- 논에는 반지름이 R인 원형 물웅덩이가 G개 있다. 줄은 어떤 물웅덩이의 내부나 경계를 지나면 안 된다.
조건을 모두 만족하면서 연결할 수 있는 줄의 최대 개수를 구하라.
입력
첫째 줄에 기둥의 개수 N (1 ≤ N ≤ 150), 물웅덩이의 개수 G (0 ≤ G ≤ 100), 물웅덩이의 반지름 R (1 ≤ R ≤ 100,000)이 주어진다.
다음 N개의 줄에는 각 기둥의 좌표 x, y가 주어진다. 이어서 G개의 줄에는 각 물웅덩이 중심의 좌표 x, y가 주어진다.
모든 좌표는 0 이상 1,000,000 이하의 정수이며, 입력에 등장하는 좌표점은 모두 서로 다르다. 주어진 기둥들은 하나의 볼록 다각형의 꼭짓점이다.
출력
연결할 수 있는 줄의 최대 개수를 출력한다.