#P18153. Ancient Country

Ancient Country

Ancient Country

古代有许多战争。为了防御,城市需要被一圈凸多边形形状的城墙包围。某个古国的国王决定修建若干城市,并为每座城市建墙,请帮助他获得最高的国家防护值。

古国的领土是一个简单多边形 P1P2…PnP_1P_2\dots P_n。多边形内部及边界上的所有点都受国家控制。多边形顶点互不相同,任意两条边除相邻边在公共端点处相触外不相交、不相触;任意两条相邻边不共线。

多边形的每个顶点 PiP_i 上都有一座塔。

最初国内没有城市。国王可以在国内建造城市 Pi1Pi2…PikP_{i_1}P_{i_2}\dots P_{i_k},当且仅当:

  • 这些点是多边形互不相同的顶点;
  • 多边形 Pi1…PikP_{i_1}\dots P_{i_k} 是凸的且面积为正;城市相邻墙允许共线;
  • 按逆时针方向遍历城市边界时,点的出现顺序正是 Pi1,Pi2,…,PikP_{i_1},P_{i_2},\dots,P_{i_k};
  • 城市边界上除这些点外没有其它塔;
  • 城市内部及边界上的所有点都受国家控制,即整个城市多边形都位于国家多边形内部或边界上。

给定两个非负整数 w,cw,c。城市的防护值为

$$2\cdot\operatorname{area}(P_{i_1}\dots P_{i_k})+w\cdot k+c.$$

国家的防护值是所有城市防护值之和。

国王希望选出若干城市,使得任意两座城市没有公共点(包括边界)。国家中某些区域可以不被任何城市覆盖。

求国家防护值的最大值。

注意:国界相邻边不共线的保证只针对国家多边形;城市允许相邻城墙共线。

输入格式

第一行一个整数 nn(3≤n≤2003\le n\le 200)。

接下来 nn 行,每行两个整数 xi,yix_i,y_i(∣xi∣,∣yi∣≤106|x_i|,|y_i|\le 10^6),按逆时针顺序给出多边形顶点。

最后一行两个整数 w,cw,c(0≤w,c≤10130\le w,c\le 10^{13})。

输出格式

输出一个整数,表示最大防护值。

样例 1

输入:

6
0 0
1 -1
1 2
0 1
-1 2
-1 -1
1 2

输出:

16

样例 2

输入:

12
0 0
1 1
2 0
4 1
5 0
5 1
8 0
9 1
10 0
11 1
5 5
1 4
3 1000000

输出:

3000063

样例 3

输入:

12
0 0
1 1
2 0
4 1
5 0
5 1
8 0
9 1
10 0
11 1
5 5
1 4
0 9

输出:

61

三个样例的一组最优方案如下,塔的编号从1开始:

  • 样例1:城市{1,5,6}和{2,3,4}。
  • 样例2:城市{2,3,4}、{6,7,11,12}和{8,9,10}。
  • 样例3:城市{2,4,6,8,10,11,12}。