거울

농부 존(Farmer John)의 소들이 농장 곳곳에서 너무 많은 말썽을 부려서, FJ는 소들을 더 주의 깊게 지켜보고 싶어졌다. 존은 농장의 여러 위치에 N개 (1 <= N <= 200)의 반사 울타리를 설치하여, 위치 (0,0)의 집에서 위치 (a,b)의 헛간까지 볼 수 있기를 바란다.

FJ의 농장의 2차원 지도에서, 울타리 i는 정수 위치 (x_i, y_i)를 중심으로 45도 기울어진('/' 모양 또는 '\' 모양) 짧은 선분으로 나타난다. 예를 들어 위치 (3,5)에 '/' 방향으로 놓인 울타리는 (2.9,4.9)에서 (3.1,5.1)까지의 선분으로 표현할 수 있다. 각 울타리(그리고 헛간의 위치)는 -1,000,000...1,000,000 범위의 정수 좌표를 가지는 서로 다른 위치에 있다. (0,0)이나 (a,b)에 있는 울타리는 없다.

FJ는 위치 (0,0)의 집에 앉아 정확히 오른쪽(+x 방향)을 바라볼 계획이다. 시선이 농장의 반사 울타리들에 반사되면서 점 (a,b)를 볼 수 있기를 바란다. 안타깝게도 FJ는 울타리 중 하나의 방향을 잘못 놓은 것 같다고 생각한다 (예를 들어 '/' 대신 '\'). FJ의 목록에서, 방향을 뒤집으면('/'와 '\' 사이에서) FJ가 점 (a,b)를 볼 수 있게 되는 첫 번째 울타리의 번호를 출력하시오.

어떤 울타리도 뒤집지 않고 이미 점 (a,b)를 볼 수 있다면 0을 출력한다. 울타리를 최대 하나 뒤집어도 여전히 (a,b)를 볼 수 없다면 -1을 출력한다.

첫째 줄: 공백으로 구분된 세 정수 N, a, b.

둘째 줄부터 1+N번째 줄까지: i+1번째 줄은 울타리 i를 설명하며, "x_i y_i /" 또는 "x_i y_i \" 형태이다. (x_i, y_i)는 울타리 중심의 위치이고, 또는 /는 그 방향을 나타낸다.

그 울타리를 뒤집으면 FJ가 점 (a,b)를 볼 수 있게 되는 첫 번째 울타리의 번호. FJ가 이미 점 (a,b)를 볼 수 있으면 0을, 최대 하나의 울타리를 뒤집어도 (a,b)를 볼 방법이 없으면 -1을 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2012-2013 > January > Bronze