문제
요시는 작은 나방 벌레이다. 요시는 청바지 위에 서식하고 있는데, 어느 날 엄마 벌레를 찾아가기로 마음을 먹었다. 요시는 청바지를 갉아 먹으면서 앞으로 나아간다. 그런데 이 청바지는 아주 낡아서 헝겊 조각으로 군데군데 기워져 있다. 이 헝겊 조각들은 합성섬유라서 요시가 그 위를 지나갈 수 없다.
요시의 현재 위치와 엄마의 위치가 주어지고 다각형 헝겊조각에 대한 정보가 주어졌을 때 헝겊조각을 피해서 엄마에게 도달하는 최단 거리를 찾는 프로그램을 작성하라. 헝겊들은 때때로 겹치기도 한다. 또한 헝겊의 변은 면실로 꿰매져 있으므로 변위에서 이동할 수 있다. 각 헝겊조각은 볼록다각형이다.
입력
입력의 처음에는 헝겊의 수 N이 입력된다.
다음으로 요시의 위치와 엄마의 위치를 나타내는 정수 X, Y와 U, V(-10000 ≤ X, Y, U, V ≤ 10000)가 입력된다.
다음 N개의 줄에는 헝겊에 대한 정보가 주어진다.
첫 번째 정수 np는 헝겊의 꼭지점의 수를 의미하며 다음 2*np개의 정수는 헝겊 다각형의 꼭지점들의 좌표가 차례로 입력된다. 모든 헝겊의 꼭지점 수를 합하면 300을 넘지 않는다.
출력
매 줄마다 최단 거리를 소수 셋째 자리까지 나타내 출력한다. 만약 도달이 불가능하다면 -1을 출력한다.
예제
2
1 0 0 4 3
3 1 1 4 4 1 4
5.000
로그인해야 코드를 작성할 수 있어요.