poj1265 Area
2024-09-04 16:38:53
题目描述:
由于题目乱码概括一下题意:
给出一个路径,求围成多边形中内部点数、边上点数(包括顶点)以及面积。
题解:
边上点数=$\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 ;
}
最新文章
- JSOI2016R3 瞎BB题解
- linux系统下挂载windows共享目录
- hibernate异常:Could not determine type for: java.util.Set
- CentOS下安装nginx并且升级nginx到最新版
- The Use of Aliases in ElasticSearch
- HighCharts学习
- Web性能优化方案
- Linux入门篇(四)——Vim的使用与Bash
- BZOJ 2748: [HAOI2012]音量调节【二维dp,枚举】
- 管理Mac的Python环境
- Android获得控件在屏幕中的绝对坐标
- 在IDEA中以TDD的方式对String类和Arrays类进行学习
- 最新版的Chrome如何始终开启flash而不是先询问?
- Android 性能优化 SparseArray【转载】
- B1029 旧键盘 (20 分)
- 移动端rem自适应布局(切图)
- [转]清除服务器IIS缓存的常用方法
- mysql 不能插入中文和显示中文
- Laravel 返回 JSON 格式
- dojo之配置dojoconfig