问题 4886 --3.多边形

4886: 3.多边形

题目描述

  平面上有一些点,其中,每个点有一个出现的概率。
现在请你需要在这些点中选择一些点顺次连接组成一个闭合的多边形,并且只能选择出现的点作为多边形的顶点,求多边形面积的最大值的期望。
如果多边形退化为点或直线,或是所有点都没有出现,则面积视作 $0$。

保证不出现三点共线。

输入

第一行包含一个正整数 $n$,表示点的个数。
接下来 $n$ 行,每行包含三个数,表示一个点。前两个整数 $x,y$ 表示点的坐标,第三个实数 $p$ 表示该点出现的概率,$p$ 最多有四位小数。

输出

输出一个实数表示期望面积。
你的答案与标准答案的差的绝对值在 $10^{-5}$ 之内,即为正确。

样例输入输出

输入#1 复制
4
0 1 0.1
0 0 0.1
1 0 0.1
1 1 0.1
输出#1 复制
0.0019

提示

对于 $30\%$ 的数据, $N \leq 3$;
对于 $100\%$ 的数据, $1 \leq N \leq 100, |x|,|y| \leq 1000, 0 \leq p \leq 1$。

序号 标题 作者 发表时间 费用 订购数 操作