시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
12 초 256 MB 1 1 1 100.000%

문제

2차원 세상에는 1에서 N까지의 번호가 붙은 N개의 신호소가 있다. 신호소 i는 어떤 좌표 (xi, yi)를 중심으로 하는 원 영역에 신호를 보낼 수 있는데, 신호소에 들어오게 되는 전력량에 따라 그 세기와 반경이 달라진다. 정확히는 신호소 i는 (i, 1), ..., (i, Mi)로 이름 붙여진 Mi개의 서로 다른 신호를 보낼 수 있다. 신호 (i, j)는 ri,j의 반경을 가지는 세기 si,j의 신호이며, wi,j이상의 전력이 신호소 i에 들어오게 될 때 무조건적으로 신호를 보내게 되어 있다.

어떤 좌표 (x, y)에 전해지는 신호의 세기는 현재 존재하는 신호들 중에서 (x, y)를 포함하는 신호들 중 세기가 가장 큰 신호의 세기가 된다. 정부는 아래의 값 A가 신호가 세상에 퍼진 정도를 나타낼 수 있다고 생각한다.

Σ (신호 세기 s) × (신호 세기가 s인 부분의 넓이)

그리고 얼마 전부터 정부는 정책적으로 신호소 i에 들일 전력량을 매일 [Li, Ui] 구간의 정수 중 하나를 동일한 확률로 선택한다. 이 때 A의 기댓값을 구하여 보자.

입력

첫 번째 줄에 신호소의 개수를 의미하는 자연수 N (1 ≤ N ≤ 20)이 주어진다.

다음에는 N개의 신호소에 대한 정보가 주어진다. 각 신호소 마다 첫 번째 줄에는 다섯 개의 정수 x, y (-104 ≤ x, y ≤ 104), M (1 ≤ M ≤ 20), L, U (1 ≤ L ≤ U ≤ 104)가 공백으로 구분되어 주어지고 다음 M개의 줄에는 세 개의 정수 r, s, w (1 ≤ r, s, w ≤ 104)가 공백으로 구분되어 주어진다.

출력

A의 기댓값을 출력한다. 정답과의 절대오차 혹은 상대오차가 10-8이하인 경우 정답으로 인정된다.

예제 입력

2
0 0 2 1 2
1 2 1
2 1 2
1 0 2 1 2
1 2 1
2 1 2

예제 출력

16.732780900043

예제 입력 2

2
0 0 1 1 2
1 1 2
0 0 1 1 2
1 1 2

예제 출력 2

2.356194490192

힌트

출처

Contest > kriiicon > 제 2회 kriiICPC R번