파일 업로드

멧돼지 감시 거울

profile
실행 시간 제한메모리 제한
1 초128 MB
📃 해결할 문제

최근 멧돼지들이 농장을 침입해 여러 가지 문제를 일으키고 있어서, 상훈은 농장을 주의깊게 관찰하고 싶어합니다. 그는 농장의 여러 위치에 반사 거울이 달린 울타리 N(1 <= N <= 200)개를 설치함으로써 집 (0,0)에서 헛간(a,b)까지 보려고 합니다.

상훈의 농장의 2D 지도에서 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)에 놓여 있지 않습니다.

상훈은 (0,0) 위치의 집에 앉아서 바로 오른쪽 (+x 방향)을 직접 바라봅니다. 그러면 그의 시선이 농장의 몇몇 반사 울타리에서 반사되어서 (a,b)를 볼 수 있습니다. 상훈은 현재 자신의 울타리 중 하나의 방향이 잘못되었다고 생각합니다 (예를 들어, '\' 대신 '/'). 

상훈이 (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)는 울타리의 중심 위치이며, \ 또는 /는 그것의 방향을 나타냅니다.
🖨️ 출력
  • 첫 번째 줄 : 상훈이 (a,b) 지점을 볼 수 있게 만드는 첫 번째 울타리의 인덱스입니다. 만약 상훈이 이미 (a,b) 지점을 볼 수 있다면 0을 출력하고, 하나의 울타리를 바꿔도 그가 (a,b) 지점을 볼 수 없는 경우 -1을 출력합니다.

💻 예제 입력 1
5 6 2
3 0 /
0 2 /
1 2 /
3 2 \
1 3 \
🖨️ 예제 출력 1
4

출처: USACO 2013 January Contest, Bronze Problem 1. Mirrors