#P18153. Ancient Country
Ancient Country
Ancient Country
古代有许多战争。为了防御,城市需要被一圈凸多边形形状的城墙包围。某个古国的国王决定修建若干城市,并为每座城市建墙,请帮助他获得最高的国家防护值。
古国的领土是一个简单多边形 。多边形内部及边界上的所有点都受国家控制。多边形顶点互不相同,任意两条边除相邻边在公共端点处相触外不相交、不相触;任意两条相邻边不共线。
多边形的每个顶点 上都有一座塔。
最初国内没有城市。国王可以在国内建造城市 ,当且仅当:
- 这些点是多边形互不相同的顶点;
- 多边形 是凸的且面积为正;城市相邻墙允许共线;
- 按逆时针方向遍历城市边界时,点的出现顺序正是 ;
- 城市边界上除这些点外没有其它塔;
- 城市内部及边界上的所有点都受国家控制,即整个城市多边形都位于国家多边形内部或边界上。
给定两个非负整数 。城市的防护值为
$$2\cdot\operatorname{area}(P_{i_1}\dots P_{i_k})+w\cdot k+c.$$国家的防护值是所有城市防护值之和。
国王希望选出若干城市,使得任意两座城市没有公共点(包括边界)。国家中某些区域可以不被任何城市覆盖。
求国家防护值的最大值。
注意:国界相邻边不共线的保证只针对国家多边形;城市允许相邻城墙共线。
输入格式
第一行一个整数 ()。
接下来 行,每行两个整数 (),按逆时针顺序给出多边形顶点。
最后一行两个整数 ()。
输出格式
输出一个整数,表示最大防护值。
样例 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}。