首页 > 代码库 > 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公式