「BZOJ1132」[POI2008] Tro

2014年10月11日3,9920

Description

平面上有N个点. 求出所有以这N个点为顶点的三角形的面积和 N<=3000

Input

第一行给出数字N,N在[3,3000] 下面N行给出N个点的坐标,其值在[0,10000]

Output

保留一位小数,误差不超过0.1

Sample Input

5
0 0
1 2
0 2
1 0
1 1

Sample Output

7.0

题解

叉积求面积 :abs(xi*yj – yi*xj) 所以去掉绝对值,把 xi 和 xj 提出来就可以求和了

每次把最左边的点当成原点,然后剩下的极角排序,接着枚举第二个点,求叉积之和……

坐标都是整数,用long long,最后再除2

 

avatar
  Subscribe  
提醒