시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 15 7 4 33.333%

문제

AcmeCorp is always looking to expand its drilling operations.

Their latest target is a largely uninhabited area in the North of the country, known as Crossland. Since the pocket of oil is quite deep already, and new drill bits are expensive, Crossland’s oil company would like to minimise the distance drilled — which may not be vertical — to get to the valuable spot.

The elevation-contoured survey map we have obtained marks the oil pocket at (0,0), 0 metres above sea level.

입력

  • One line containing one positive integer N, the number of polygon-shaped contour lines.
  • N more lines each containing two integers, H0 and H1 (0 ≤ H0, H1 ≤ 106), the height of land in metres above sea level outside and inside the contour respectively, followed by a positive integer Mi representing the number of vertices of this contour.
  • The remaining 2 · Mi integers on each line are distinct coordinate pairs (xj, yj) (−106 ≤ x, y ≤ 106) denoting the jth point on the contour. No two contour lines touch, nor does a contour line touch the point (0,0).

The total number of points across all contours will not exceed 105, and it is guaranteed that the outer height of a contour is always equal to the inner height of its containing contour, if one exists.

출력

The first and only line of output should contain one real number indicating the closest slanted distance from the surface to the target. Your answer should be correct up to an absolute or relative precision of 10−6.

예제 입력

2
5 8 4 -2 0 0 -3 2 0 0 3
8 10 4 -1 -1 1 -1 1 1 -1 1

예제 출력

5.2696518641

예제 입력 2

1
8 9 3 -14 -14 14 -14 0 20

예제 출력 2

9

예제 입력 3

1
2 1 8 -4 -4 -1 -3 -2 2 2 2 1 -3 4 -4 3 4 -3 4

예제 출력 3

1.8605210188

힌트