题目描述
宫水三叶擅长手工，比如用绳子围住一个带钉子的木板。
这是一个很大的木板，我们可以用一个平面直角坐标系来描述它。
木板上面有 $n$ 个钉子，第 $i$ 个钉子的坐标为 $(x_i,y_i)$ 。
三叶可以用一些绳子连接一些点，这些绳子连接的点有一个限制。
首先，这些绳子连成的图形必须要是一个封闭的凸多边形。其次，绳子可能经过除端点外的其它点，但是没有两条绳子在同一条**直线**上。**形象化的说，这是一个凸包，使用的绳子数就是边数**。
对于一个图形，我们可以把所有钉子分成三类。
1、凸包的顶点。
2、在凸包内或在凸包边上，但是不是凸包顶点。
3、不在凸包内。
假设这三类点分别有 $x,y,z$ 个，那么三叶认为这个图形的价值为 $x cdot a^x cdot b^y cdot c^z$ ，其中 $a,b,c$ 为给定的三个整数，它们之间有个特殊的关系 $a+c=b$ 。
三叶想知道，对于所有不同的图形，它们各自的价值的总和是多少。
两个图形 $A,B$ 不同，只需要满足其中某一条绳子在 $A$ 中出现并且在 $B$ 中没出现或者在 $B$ 中出现并且在 $A$ 中没出现。
数据范围
$1 le n le 2 imes 10^3,0 le x_i,y_i le 10^9,1 le a,b,c le 10^9$
题解
考虑到 $b=a+c$ 有什么用，思考组合意义，把每个点设为 $b$ 个状态，其中 $a$ 个为 $1$ 状态， $c$ 个为 $0$ 状态。那答案就为选择状态为 $1$ 的点构成的凸包的边权和。
那就可以考虑枚举一条边，这条边有贡献的话就是一侧全为 $0$ ，一侧都可的情况，按照极角排序，维护队列即可。
效率： $O(n^2logn)$ 。