레이저와 거울

무슨 이유에서인지, 농부 존의 소들은 늘 레이저 조명 쇼를 벌이는 것처럼 보인다.

최근 쇼를 위해 소들은 크고 강력한 레이저를 구해 왔다. 어찌나 큰지 배달된 자리에서 쉽게 옮길 수조차 없을 정도이다. 소들은 이 레이저의 빛을 어떻게든 존의 사유지 반대편에 있는 헛간까지 보내고 싶다. 레이저와 헛간은 모두 존의 농장 지도 위 2차원 평면의 점으로 볼 수 있다. 소들은 레이저가 수평 또는 수직 방향(즉, x축 또는 y축에 평행한 방향)으로 광선을 쏘도록 조준할 계획이다. 그런 다음 이 광선을 여러 개의 거울에 반사시켜 헛간까지 유도할 것이다.

농장에는 서로 다른 2차원 점(레이저 및 헛간과도 다른 위치)에 \(N\)개의 울타리 기둥(\(1 \leq N \leq 100,000\))이 있으며, 소들은 여기에 거울을 설치할 수 있다. 어떤 기둥에는 거울을 설치하지 않을 수도 있는데, 이 경우 레이저는 방향을 바꾸지 않고 그 기둥 위를 그대로 지나간다. 기둥에 거울을 설치한다면 / 또는 모양으로 대각선 방향으로 정렬하여, 수평 방향의 광선을 수직 방향으로, 또는 그 반대로 방향을 바꾸게 한다.

레이저를 헛간까지 유도하기 위해 소들이 사용해야 하는 거울의 최소 개수를 계산하시오.

문제 출제: 브라이언 딘(Brian Dean)

문제 출제: 브라이언 딘(Brian Dean)

입력의 첫째 줄에 공백으로 구분된 다섯 정수 \(N, x_L, y_L, x_B, y_B\)가 주어진다. \((x_L, y_L)\)은 레이저의 위치이고 \((x_B, y_B)\)는 헛간의 위치이다. 모든 좌표는 \(0\) 이상 \(1,000,000,000\) 이하이다.

다음 \(N\)개의 줄에는 각 울타리 기둥의 \(x\), \(y\) 위치가 주어지며, 두 값 모두 \(0 \ldots 1,000,000,000\) 범위의 정수이다.

레이저를 헛간까지 유도하는 데 필요한 거울의 최소 개수를 출력한다. 불가능하다면 -1을 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > December > Gold