首页 > 代码库 > POJ 1265 Area Pick公式
POJ 1265 Area Pick公式
题目大意:给出一个多边形的轮廓(以边的向量形式给出),求:1.有多少个整点在这个图形里面,2.有多少个点在图形内部,3.图形的面积是多少。
思路:首先明确Pick公式:
公式意义并不是让我们求出这个多边形的面积是多大,一是因为面积没必要用Pick公式求,二是没法求出多边形中间有多少整点。但是面积可以用叉积来求,多边形边上的整点可以用gcd来求,这样经过稍微的变形,就可以求解多边形中间有多少个整点了。
CODE(c++AC,g++WA,求高人指点):
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Point{ int x,y; Point(int _ = 0,int __ = 0):x(_),y(__) {} Point operator +(const Point &a)const { return Point(x + a.x,y + a.y); } }; int cases; int points; inline int Cross(const Point &a,const Point &b) { return a.x * b.y - a.y * b.x; } int GCD(int x,int y) { return y ? GCD(y,x % y):x; } int main() { for(cin >> cases; cases; --cases) { scanf("%d",&points); int on_side = 0,area = 0; Point now,dir,_next; for(int i = 1; i <= points; ++i) { scanf("%d%d",&dir.x,&dir.y); on_side += GCD(abs(dir.x),abs(dir.y)); _next = (now + dir); area += Cross(now,_next); now = _next; } area = abs(area); static int T = 0; printf("Scenario #%d:\n",++T); printf("%d %d %d.%d\n\n",(area + 2 - on_side) / 2,on_side,area >> 1,((area&1) ? (5):(0))); } return 0; }
POJ 1265 Area Pick公式
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。