#P17809. [ONTAK 2023]OLI

[ONTAK 2023]OLI

题目描述

一座种植园的边界是一个简单多边形,其顶点均为整点。多边形严格内部的每个整点上都有一棵橄榄树。

你要用 n−3n-3 条两两不在内部相交的合法对角线,将多边形划分成 n−2n-2 个三角形。新增对角线上的树都要被移除。求划分后可以保留的树的最大数量,也就是所有三角形严格内部整点数之和。

多边形不一定是凸多边形。

输入格式

第一行一个整数 nn。接下来 nn 行,每行两个整数 xi,yix_i,y_i,按沿边界的顺序给出顶点;顺时针和逆时针均可能出现。

输出格式

输出能够保留的树的最大数量。

数据范围

3≤n≤3003\le n\le300,∣xi∣,∣yi∣≤109|x_i|,|y_i|\le10^9。保证多边形简单,且任意三个顶点不共线。

样例

5
0 -4
9 0
1 8
3 2
-2 1
44
4
0 0
0 2
2 2
2 0
0