UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2349. [Baltic2011]Polygon

统计 下载数据

Description

一个有N个顶点的简单多边形,画在一个无限大的矩形网格中。对于这样的多边形,只有相邻的两边在它们共同的顶点处相交;没有其它边相交或有接触。该多边形的顶点都在网格的网点上,也就是说,多边形的顶点都是整数坐标。

你的任务是得到严格地处于给定的多边形中的网格线的总长度(这些网格的线段片段在下面的图中着重描出了)。

Input

 
第一行包括一个整数N,即多边形的顶点数。
以下N行包括2个整数xy,即顶点的坐标。顶点将按顺时针或逆时针顺序给出。所有顶点均不相同,但可能有连续2个以上的顶点是在同一条直线上的。

Output

 
输出只有一行,给出一个带小数部分的数(decimal number):严格地处于给定的多边形中的网格线的总长度。
数据范围
3≤ N ≤100 000
-500 000 000≤ x, y ≤500 000 000
50分的数据点中,所有多边形的边都处于网格线上。
评分
若你的输出与标准答案足够接近即可判正确。
更准确地说:假设你的输出为L,标准答案为R。那至少以下两个条件至少要有一条成立:
l      |L - R|≤R∙10-6(相对精确)
l      |L - R|≤10-6(绝对精确)
 

Sample Input

3
5 1
2 4
1 1

Sample Output

10.0

Hint



水平的线段总长度为4/3+8/3=4,垂直的线段总长度为3+2+1=6。总长度为4+6=10

Source