#P17809. [ONTAK 2023]OLI
[ONTAK 2023]OLI
题目描述
一座种植园的边界是一个简单多边形,其顶点均为整点。多边形严格内部的每个整点上都有一棵橄榄树。
你要用 条两两不在内部相交的合法对角线,将多边形划分成 个三角形。新增对角线上的树都要被移除。求划分后可以保留的树的最大数量,也就是所有三角形严格内部整点数之和。
多边形不一定是凸多边形。
输入格式
第一行一个整数 。接下来 行,每行两个整数 ,按沿边界的顺序给出顶点;顺时针和逆时针均可能出现。
输出格式
输出能够保留的树的最大数量。
数据范围
,。保证多边形简单,且任意三个顶点不共线。
样例
5
0 -4
9 0
1 8
3 2
-2 1
44
4
0 0
0 2
2 2
2 0
0