首页 > 代码库 > tyvj 1150 绳子围点 Pick定理 防溢出策略
tyvj 1150 绳子围点 Pick定理 防溢出策略
P1150 - 绳子围点
From 332404521 Normal (OI)总时限：10s 内存限制：128MB 代码长度限制：64KB
背景 Background
最近小小鱼在研究平面几何，遇到一个难题，怎么也想不出来，于是找到大牛你来帮他做。描述 Description
给出平面上n个点，所有点的坐标都是整数，小小鱼用一条绳子围成一个封闭图形，把这些点全部围在里面，并且所用绳子长度最短。围好了之后，小小鱼想知道这条绳子总共围住了多少个横、纵坐标都为整数的点（包括给出的n个点和未给出的点，绳子刚好穿过的点也算围在内），但是数着满平面的点，小小鱼晕了过去>.<。输入格式 InputFormat
第一行一个整数n（n<=200000），表示给出点的个数。以下n行每行两个整数xi,yi（都在longint范围内），表示给出第i个点的坐标。
输出格式 OutputFormat
一行，一个整数，表示绳子所围住的横纵坐标都为整数的顶点个数。样例输入 SampleInput [复制数据]
4
-1 -1
1 3
3 1
1 1
样例输出 SampleOutput [复制数据]
10
数据范围和注释 Hint
样例中最短的绳子围法是三个顶点分别为(-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。
来源 Source
小小鱼pick定理S=I+（A/2）-1;
s是面积，I是多边形内部整点，A是边上整点;
A 用GCD求，注意0的情况。
这道题是一道数据量极大，极易出现long long 溢出的题，下面就总结一下这类题要注意的：
- 两个[-1e9,1e9]内的int相减会溢出，主要出现再几何题中
- 如果在取模题目中，有减运算，注意最后要把他变成正数
- 1e9的数据范围忌用double
tyvj 1150 绳子围点 Pick定理 防溢出策略
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。