题目描述:

vjudge

POJ

由于题目乱码概括一下题意:

给出一个路径,求围成多边形中内部点数、边上点数(包括顶点)以及面积。

题解:

边上点数=$\sum gcd(dx,dy)$

$Pick$定理:设$a$表示内部点数,$b$表示边上点数(包括顶点),$S$表示面积。则$$S=a+ \frac{ b }{ 2 } -1$$

代码:

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = ;
struct Point
{
ll x,y;
Point(){}
Point(ll x,ll y):x(x),y(y){}
Point operator + (const Point&a)const{return Point(x+a.x,y+a.y);}
Point operator - (const Point&a)const{return Point(x-a.x,y-a.y);}
ll operator ^ (const Point&a)const{return x*a.y-y*a.x;}
};
typedef Point Vector;
int T,n;
Point p[N];
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
void work(int Sce)
{
scanf("%d",&n);
ll S = ,b = ;
Point s0(,),s1(,),s2(,);
Vector v;
for(int i=;i<=n;i++)
{
scanf("%I64d%I64d",&v.x,&v.y);
ll x = v.x,y = v.y;
if(x<)x=-x;
if(y<)y=-y;
b += gcd(x,y);
s1 = s2,s2 = s2 + v;
S += ((s1-s0)^(s2-s0));
}
if(S<)S=-S;
ll a = (S+-b)/;
printf("Scenario #%d:\n",Sce);
printf("%I64d %I64d ",a,b);
if(S&)printf("%I64d.5\n\n",S/);
else printf("%I64d.0\n\n",S/);
}
int main()
{
scanf("%d",&T);
for(int i=;i<=T;i++)work(i);
return ;
}

最新文章

  1. JSOI2016R3 瞎BB题解
  2. linux系统下挂载windows共享目录
  3. hibernate异常:Could not determine type for: java.util.Set
  4. CentOS下安装nginx并且升级nginx到最新版
  5. The Use of Aliases in ElasticSearch
  6. HighCharts学习
  7. Web性能优化方案
  8. Linux入门篇(四)——Vim的使用与Bash
  9. BZOJ 2748: [HAOI2012]音量调节【二维dp,枚举】
  10. 管理Mac的Python环境
  11. Android获得控件在屏幕中的绝对坐标
  12. 在IDEA中以TDD的方式对String类和Arrays类进行学习
  13. 最新版的Chrome如何始终开启flash而不是先询问?
  14. Android 性能优化 SparseArray【转载】
  15. B1029 旧键盘 (20 分)
  16. 移动端rem自适应布局(切图)
  17. [转]清除服务器IIS缓存的常用方法
  18. mysql 不能插入中文和显示中文
  19. Laravel 返回 JSON 格式
  20. dojo之配置dojoconfig

热门文章

  1. [Java]HashSet的工作原理
  2. asp.net 多语言 在IIS7.5发布出现找不到资源文件
  3. Mysql修改server uuid
  4. js页面可视区域懒加载
  5. php设计模式-单例
  6. vuejs 组件 移动端push 没有渲染页面
  7. restful之http讲解
  8. ABAP事件的简单用法
  9. JavaScript笔记6-数组新方法
  10. C语言的time函数和localtime函数