레이팅 미적용모두 알다시피, 소 베시(Bessie)는 농장에서 말썽을 부리는 것을 무엇보다 좋아한다. 베시가 너무 큰 사고를 치지 못하도록, 농부 존(Farmer John)은 긴 밧줄로 베시를 울타리에 묶어 두기로 했다. 위에서 내려다보면 울타리는 수직선을 따라 배열된 N개 (1 <= N <= 10)의 기둥으로 이루어져 있고, 베시의 위치 (bx, by)는 이 수직선의 오른쪽에 있다. FJ가 베시를 묶는 데 사용한 밧줄은 M개 (3 <= M <= 10,000)의 선분의 수열로 표현되며, 첫 번째 선분은 베시의 위치에서 시작하고 마지막 선분은 베시의 위치에서 끝난다. 어떤 울타리 기둥도 이 선분들 위에 있지 않다. 하지만 선분들은 서로 교차할 수 있고, 여러 선분이 끝점에서 겹칠 수도 있다.
베시의 탈출을 돕기 위해, 나머지 소들이 헛간에서 톱을 훔쳐 왔다. 베시가 밧줄에서 벗어날 수 있으려면(즉, 밧줄이 어떤 울타리 기둥에도 걸리지 않은 채 오른쪽으로 도망칠 수 있으려면) 잘라서 제거해야 하는 울타리 기둥의 최소 개수를 구하시오.
입력의 모든 (x,y) 좌표(울타리 기둥, 베시, 선분 끝점)는 0..10,000 범위이다. 모든 울타리 기둥의 x 좌표는 같고, bx는 이 값보다 크다. (이 문제의 그림은 생략되었다.)
첫째 줄: 공백으로 구분된 네 정수 N, M, bx, by.
둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 울타리 기둥 i의 x 좌표와 y 좌표가 공백으로 구분되어 주어진다.
2+N번째 줄부터 2+N+M번째 줄까지: 이 M+1개의 줄에는 밧줄 위의 점의 x 좌표와 y 좌표가 공백으로 구분되어 순서대로 주어진다. 첫 번째 점과 마지막 점은 항상 베시의 위치 (bx, by)와 같다.
베시가 오른쪽으로 달려 탈출할 수 있도록 제거해야 하는 기둥의 최소 개수.
tied.in · 출력을 쓸 파일 tied.out2 10 6 1
2 3
2 1
6 1
2 4
1 1
2 0
3 1
1 3
5 4
3 0
0 1
3 2
6 11Input details: There are two posts at (2,3) and (2,1). Bessie is at (6,1).
Output details: Removing either post 1 or post 2 will allow Bessie to escape.