首页 > 代码库 > LightOj1418 - Trees on My Island（Pick定理）
LightOj1418 - Trees on My Island（Pick定理）
题目链接：http://lightoj.com/volume_showproblem.php?problem=1418
题意：给你多边形中的顶点，n个点按顺时针或逆时针方向给出，然后求出多边形内部有多少个整数点；
皮克定理：
在一个多边形中。用I表示多边形内部的点数，E来表示多边形边上的点数，S表示多边形的面积。
满足：S = I + E/2 - 1;
求E，一条边（x1, y1, x2, y2）上的点数（包括两个顶点）= gcd(abs(x1-x2),abs(y1-y2));
#include<iostream>#include<algorithm>#include<math.h>#include<string.h>#include<stdio.h>#include<queue>using namespace std;#define met(a, b) memset(a, b, sizeof(a))#define mod 1000000007typedef long long LL;////////////////////////////////////////////////////////////////////////////////////////////////*HDU2036题意：有一个多边形，含有n个顶点，按逆时针方向依次给出，求对应的多边形的面积;*/const int N = 10005;struct point{ LL x, y; point(){} point(LL x, LL y):x(x), y(y) {} friend LL operator ^(point p, point q) { return p.x*q.y - p.y*q.x; };}p[N];LL gcd(LL a, LL b){ return b==0?a:gcd(b, a%b);}int main(){ int n, T, t = 1; scanf("%d", &T); while(T--) { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%lld %lld", &p[i].x, &p[i].y); p[0] = p[n]; LL S = 0, E = 0; for(int i=1; i<=n; i++) { S += p[i]^p[i-1]; E += gcd(abs(p[i].x-p[i-1].x), abs(p[i].y-p[i-1].y)); } LL I = (abs(S)- E)/2 + 1; printf("Case %d: %lld\n", t++, I); } return 0;}/*IN:191 22 14 14 36 26 44 51 52 3OUT:Case 1: 8*/
LightOj1418 - Trees on My Island（Pick定理）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。