감옥 담장 세우기
시간 제한2초메모리 제한128 MB
감옥 지점과 이를 둘러싼 N개의 기둥이 주어질 때, 서로 겹치지 않고 감옥을 완전히 감싸는 중첩된 다각형 벽을 최대 몇 겹까지 세울 수 있는지 구하는 문제입니다.
문제
소들은 위치 (Px, Py)에 감옥을 세우고, 그 주위에 가능한 한 많은 겹의 담을 만들려고 한다. 감옥은 하나의 점으로 취급한다.
감옥 주변에는 N개의 담 기둥이 주어진다. 하나의 담은 여러 개의 담벼락이 이어진 닫힌 다각형이며, 각 담벼락의 양 끝점은 반드시 주어진 담 기둥이어야 한다.
각 담은 감옥을 완전히 둘러싸야 한다. 또한 어떤 담이 다른 담의 안쪽에 조금이라도 들어가 있다면, 바깥쪽 담은 그 안쪽 담 전체도 완전히 둘러싸야 한다. 서로 다른 두 담은 교차하거나 한 점에서 만나면 안 되며, 담벼락이나 담 기둥을 공유할 수도 없다. 즉, 서로 다른 담 사이에는 항상 양의 넓이를 가진 빈 공간이 있어야 한다.
감옥 위치와 담 기둥을 통틀어 어떤 세 점도 한 직선 위에 있지 않다. 주어진 담 기둥만 사용하여 만들 수 있는, 서로 겹치지 않는 중첩된 담의 최대 겹 수를 구하시오.
입력
첫째 줄에 정수 N, Px, Py가 주어진다.
1 <= N <= 1,000
-100,000 <= Px, Py <= 100,000
다음 N개의 줄에는 담 기둥의 좌표 x, y가 한 줄에 하나씩 주어진다. 각 좌표의 절댓값은 100,000을 넘지 않는다.
출력
만들 수 있는 중첩된 담의 최대 겹 수를 한 줄에 출력한다.