凸包

Description

给定平面上n个点及其出现的概率,问这n个点中出现的那些点组成的凸包面积期望是多少,如果凸包退化为直线则视其面积为0。保证不出现三点共线。

Format

Input

第一行,一个整数N,表示点的个数。
第2~N+1行,每行三个数。前两个整数x,y表示点的坐标。第三个实数p,表示出现的概率。p最多有4位小数。

Output

一行一个实数,表示期望面积。
答案保留6位小数。

Sample 1

Input

3
0 0 0.1
1 0 0.1
1 1 0.1

Output

0.000500

样例解释:
对于三个点都出现的情况才有可能出现凸包。该凸包的面积为0.5。
所以期望面积为0.1 * 0.1 * 0.1 * 0.5 =0.000500

Limitation

对于30%的数据,N <= 3
对于100%的数据,N <= 100, -1000 <= x,y <= 1000, 0 <= p <= 1。
1s, 256MiB for each test case.