시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 2314 | 787 | 564 | 32.545% |
소들의 반란이 있은 뒤, 이 소들은 포로로 잡은 인간들을 감시해야 했다. 소들은 (Px, Py)의 위치에 감옥을 짓고, 감옥 둘레에 가능한 한 여러 겹으로 담을 쌓아 포로들이 도망가기 힘들도록 하려 한다. 감옥은 하나의 점으로 표현된다.
이러한 목적을 달성하기 위해, 소들은 감옥 주변에 N개의 담 기둥을 세웠다. 각각의 담은 감옥을 완전히 감싸야 하고, 담 안에 (부분적으로라도) 포함되는 담이 있다면 이러한 담도 완전히 감싸야 한다. 즉, 담벼락이 교차하거나 한 점에서 만나서는 안 된다. 감옥과 담 기둥 중 어느 세 점도 일직선상에 있지 않다.
이러한 담 기둥들이 주어졌을 때, 겹치지 않는 최대의 중첩된 담의 겹 수를 구하는 프로그램을 작성하시오.
담은 여러 개의 담벼락이 연결된, 닫힌 다각형을 의미하고, 각각의 담벼락의 두 끝 점은 담 기둥 이어야 한다. 이러한 담 사이에는 반드시 약간이라도 공간이 있어야 한다. 즉, 서로 다른 두 담이 하나의 담벼락이나 담 기둥을 공유해서는 안 된다.
첫째 줄에 N(1 ≤ N ≤ 1,000), Px, Py (-100,000 ≤ Px, Py ≤ 100,000)이 주어진다. 다음 N개의 줄에는 차례로 담 기둥의 좌표가 주어진다. 각각의 좌표는 절댓값이 100,000을 넘지 않는 정수이다.
첫째 줄에 최대 겹 수를 출력한다.
8 -1 0 2 2 2 -2 -2 2 -2 -2 0 10 8 0 -12 1 1 -5
2
Olympiad > USA Computing Olympiad > 2002-2003 Season > USACO January 2003 Contest > Green 3번