19650번 - 개미여행 스페셜 저지

지금 개미 마을에서는 싸움이 일어났다! 다양한 소속의 개미들이 열심히 싸우고 있다. 싸움을 싫어하는 철수 개미는 다른 개미들이 싸우는 것에 신경 쓰지 않고 여행을 가려고 한다.

철수는 (s_x, s_y)에서 (e_x, e_y)로 이동하려고 한다. 만약 철수가 어떤 소속에 포함되었다는 오해를 사게 되면 철수는 싸움에 휘말리게 되고 평화로운 여행 계획은 망하게 된다.

구체적으로는, 특정 그룹 내에 있는 임의의 서로 다른 개미 3마리를 골랐을 때, 그 개미들을 꼭짓점으로 하는 삼각형 안에 있다면 철수는 그 그룹의 소속이라는 오해를 사게 된다. 삼각형 테두리를 지나는 것은 허용되고 특정 그룹 내에 있는 임의의 개미 3마리를 골랐을 때 개미들이 한 직선 위에 있는 경우는 없다.

철수가 해당 오해를 사는 일 없이 (e_x, e_y)에 최단 거리로 이동한다고 했을 때 철수가 이동하는 거리는 얼마인가?

첫 줄에는 s_x, s_y, e_x, e_y가 주어진다. 다음 줄에는 소속의 개수 N이 주어진다.

다음 줄부터 N개의 소속에 대한 정보가 나타난다. 소속에 대한 정보는 여러 줄에 걸쳐 나타난다. 첫번째 줄에는 소속에 포함된 개미의 마리 수 M이 주어진다. 다음 해당 소속의 개미들의 좌표 p_x, p_y가 M줄에 걸쳐 차례로 주어진다. 문제에 있는 모든 x 좌표와 y 좌표는 절댓값이 100,000을 넘지 않는 정수이다.

철수를 제외한 개미들의 수는 100마리를 넘지 않고, 시작점과 도착점을 포함한 어떤 좌표도 같은 위치에 있지 않다.

철수가 도착점에 도달할 수 있는 경우, 철수가 이동한 거리를 출력한다. 절대/상대 오차가 10⁻⁶ 이하일 경우 정답으로 인정한다.

철수가 도착점에 도달할 수 없다면 -1을 출력한다.