问题 2750 --P1150 绳子围点

2750: P1150 绳子围点

题目描述

  给出平面上n个点,所有点的坐标都是整数,小小鱼用一条绳子围成一个封闭图形,把这些点全部围在里面,并且所用绳子长度最短。围好了之后,小小鱼想知道这条绳子总共围住了多少个横、纵坐标都为整数的点(包括给出的n个点和未给出的点,绳子刚好穿过的点也算围在内),但是数着满平面的点,小小鱼晕了过去> .< 。

输入

第一行一个整数n(n< =200000),表示给出点的个数。以下n行每行两个整数xi,yi(都在longint范围内),表示给出第i个点的坐标。

输出

一行,一个整数,表示绳子所围住的横纵坐标都为整数的顶点个数。

样例输入输出

输入#1 复制
4
-1 -1
1 3
3 1
1 1
输出#1 复制
10

提示

样例中最短的绳子围法是三个顶点分别为(-1,-1),(3,1),(1,3)的三角形其中绳子围住了以下点: (-1,-1),(0,0),(1,0),(0,1),(1,1),(2,1),(1,2),(2,2),(3,1),(1,3) 总共10个。 答案可能超过longint的范围,需要用int64或long  long。

序号 标题 作者 发表时间 费用 订购数 操作