题目描述

Noku 有 $N$ 支三角形画笔，编号为 $0,1,\ldots,N-1$。第 $i$ 支画笔是一个非退化三角形，其三个顶点分别为 $(0,0)$、$(x_{1,i},y_{1,i})$、$(x_{2,i},y_{2,i})$。

一开始，画布上的作品只有一个点。Noku 按编号从小到大依次考虑这些画笔。对于第 $i$ 支画笔，他以 $p_i/100$ 的概率使用它，各画笔是否使用彼此独立。

如果使用第 $i$ 支画笔，他不会旋转画笔，而是让画笔的顶点 $(0,0)$ 始终位于当前作品的边界上，并沿当前作品的整条边界移动一周。移动过程中画笔覆盖到的所有区域都会加入作品。

求最终作品面积的期望值。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，第 $i$ 行包含五个整数 $x_{1,i},y_{1,i},x_{2,i},y_{2,i},p_i$，表示第 $i$ 支三角形画笔以及使用它的百分比概率。

输出格式

输出一个实数，表示最终作品面积的期望值。答案的绝对误差或相对误差不超过 $10^{-6}$ 即可。

数据范围

$1\le N\le 2500$；$-100\le x_{1,i},y_{1,i},x_{2,i},y_{2,i}\le100$；每个三角形面积严格为正；$1\le p_i\le100$。

样例

3
1 2 2 -1 100
-2 3 2 -1 100
-4 -1 -2 1 100

52.5