레이저와 헛간, 최대 100,000개의 기둥이 주어질 때, 빔이 레이저에서 헛간까지 도달하도록 거울을 놓을 기둥의 최소 개수를 구한다.
소들이 또 레이저 쇼를 연다.
이번에 준비한 레이저는 너무 커서 배달된 자리에서 옮길 수 없다. 소들은 레이저 빛을 농장 반대편 헛간까지 보내려고 한다. 농장 지도에서 레이저와 헛간은 평면 위의 점이다. 소들은 빛이 x축이나 y축과 나란하게, 즉 가로나 세로로 출발하도록 레이저를 겨눈다. 그다음 거울 몇 개로 빛을 꺾어 헛간까지 보낸다.
농장에는 울타리 기둥이 NNN개 (1≤N≤100,0001 \le N \le 100{,}0001≤N≤100,000) 있고, 모두 서로 다른 점에 서 있다. 레이저나 헛간과 같은 자리에 선 기둥은 없다. 소들은 원하는 기둥에만 거울을 달 수 있다. 거울이 없는 기둥 위로는 빛이 방향을 바꾸지 않고 그대로 지나간다. 거울을 단 기둥에서는 거울이 / 또는 \ 모양으로 비스듬히 놓여서, 가로로 오던 빛을 세로로, 세로로 오던 빛을 가로로 꺾는다. 거울의 방향은 소들이 정한다.
/
\
레이저에서 나온 빛을 헛간까지 보내려면 거울이 최소 몇 개 필요한지 구하여라.
첫째 줄에 정수 다섯 개 NNN, xLx_LxL, yLy_LyL, xBx_BxB, yBy_ByB가 공백으로 구분되어 주어진다. (xL,yL)(x_L, y_L)(xL,yL)은 레이저의 위치, (xB,yB)(x_B, y_B)(xB,yB)는 헛간의 위치이다.
다음 NNN개의 줄에는 각각 울타리 기둥 하나의 좌표 xxx와 yyy가 주어진다. 모든 좌표는 000 이상 1,000,000,0001{,}000{,}000{,}0001,000,000,000 이하의 정수이다. 기둥 NNN개의 위치는 서로 다르고, 레이저와 헛간의 위치와도 다르다.
레이저 빛을 헛간까지 보내는 데 필요한 거울의 최소 개수를 출력한다. 거울을 어떻게 놓아도 빛이 헛간에 닿지 않으면 -1을 출력한다.