Random signals Batch Compilation commands

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

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

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

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

입력 형식

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

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

쉬운 문제에서는 모든 신호소에 대해 $M = 1$인 입력이 주어진다.

어려운 문제에서는 별 다른 제약이 없다.

출력 형식

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

예제 1

입력

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.356194490192