짐비는 모바일 게임 와일드 리프트를 즐겨한다. 특히 탑 라인에서 아우렐리온 솔을 즐겨 하는데, skill issue로 인해 다른 챔피언을 잘 다루지 못하기 때문이다!
울적해진 짐비는 이렐리아를 연습하기로 했다. 짐비는 미니언 사이를 연달아 돌진하는 멋진 모습을 꿈꾸며 연습장에 들어갔다.
연습장은 차원 좌표평면이다. 연습장에는 미니언 마리와 목표 허수아비가 있으며, 짐비의 시작 위치와 모든 대상의 위치가 주어진다.
짐비는 다음 규칙에 따라 돌진할 수 있다.
두 위치 사이의 거리는 두 점을 잇는 선분의 길이이다. 모든 대상은 움직이지 않으며, 돌진 경로에 있는 다른 대상은 돌진에 영향을 주지 않는다. 짐비는 돌진 이외의 방법으로는 이동할 수 없다.
짐비가 목표 허수아비에게 도달하기 위한 최소 돌진 횟수를 구해 보자.
입력은 다음과 같은 형식으로 주어진다.
첫째 줄에 목표 허수아비에게 도달하기 위한 최소 돌진 횟수를 출력한다.
도달할 수 없다면 -1을 출력한다.
순서로 돌진하면 목표 허수아비에게 도달할 수 있다.
여기서 는 짐비의 시작 위치, 는 목표 허수아비의 위치이며, 는 번 미니언의 위치이다.
이면 미니언의 위치를 나타내는 줄은 주어지지 않는다.
각 돌진의 이동 거리는 차례대로 이므로 모두 사거리 이내이다.
미니언에게 돌진할 수는 있지만, 그 위치에서도 목표 허수아비에게 돌진할 수 없다.