#P18818. [Croatian CPC2016] Ograda
[Croatian CPC2016] Ograda
[Croatian CPC2016] Ograda
题目描述
在标准平面直角坐标系中, 轴向右, 轴向上。
对于每个左下角坐标为非负整数 、边平行于坐标轴的单位正方形,定义其价值为 。其中,,对 ,。
现在用一条各边均平行于坐标轴的多边形围栏围住一片区域。请计算围栏内部所有单位正方形的价值之和,对 取模。
输入格式
第一行包含一个正整数 (),表示多边形的顶点数。
接下来 行,第 行包含两个整数 (),按沿边界的顺序给出第 个顶点。最后一个顶点与第一个顶点也相连。
保证这些顶点构成一个简单多边形,各边平行于坐标轴,且相邻的两条边从不平行。顶点可能按顺时针或逆时针顺序给出。
输出格式
输出一个整数,表示所求价值之和对 取模的结果。
样例 1
输入
4
1 1
1 2
2 2
2 1
输出
1
样例 2
输入
4
3 3
1 3
1 1
3 1
输出
9
样例 3
输入
18
0 0
2 0
2 1
3 1
3 2
5 2
5 3
4 3
4 4
3 4
3 3
2 3
2 4
0 4
0 3
1 3
1 1
0 1
输出
119
样例说明
下图展示了样例 3 的围栏及各个单位正方形的价值。
