题意：给你一个包含n个点的凸包，所有可能出现凸包的面积和。 分析：首先比较暴力的方法就是n^2枚举一条边，求它对答案的贡献。但是点的个数有10^5，因此我们考虑从某一个点出发的所有有向面积。 若我们当前考虑的是第i个点，那么它与第i+1个点形成的这条边所能产生的凸包个数为(2^(n - 2) - 1)个，与第i + 2个点形成的这条边的个数为(2 ^ (n - 3) - 1)个……又因为叉积满

题目链接：hdu 5448 Marisa’s Cake 解题思路 这题和zoj 3871 Convex Hull有点像，不过点数比较大，不能接受 o(n2) o(n^2)的算法。但是题目给定的是一个凸包，所以可以通过化简，在 o(n) o(n)的复杂度内计算出答案。 首先，对于一个三角形ABC SABC=fA×fB+fB×fC+fC×fA(fi表示点i和原点组成的向量） S_{