Pick 定理

定理内容

如果一个多边形的顶点都是整点，则有

$$A=i+\frac{b}{2}-1,$$

其中 $A$ 为面积，$i$ 为多边形严格内部的整点数量，$b$ 为多边形边界上的整点数量。

IMPORTANT

边界上的整点不只是顶点，还有边上其他的点。

例子

CF1548D1 - Gregor and the Odd Cows (Easy)

This is the easy version of the problem. The only difference from the hard version is that in this version all coordinates are even.

There are $n$ fence-posts at distinct coordinates on a plane. It is guaranteed that no three fence posts lie on the same line.

There are an infinite number of cows on the plane, one at every point with integer coordinates.

Gregor is a member of the Illuminati, and wants to build a triangular fence, connecting $3$ distinct existing fence posts. A cow strictly inside the fence is said to be enclosed. If there are an odd number of enclosed cows and the area of the fence is an integer, the fence is said to be interesting.

Find the number of interesting fences.

面积 $A$ 必然是偶数，所以假如 $i$ 是奇数，那么一定要求 $\frac{b}{2}$ 是偶数。所以，按照每个点的 $x$ 的奇偶性和 $y$ 的奇偶性共分为 4 类，直接分讨即可。