首页 > 代码库 > POJ 2954

POJ 2954

PICK定理:格子上的多边形面积=边界上格子点数/2+内部点数-1。

利用叉积求出面积。再枚举边上的点数。然后按公式求出内部点数就可以了。

关于PICK:http://blog.csdn.net/i_fuqiang/article/details/9817343

 

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;int x1,x2,x3,yy1,y2,y3;int main(){	while(cin>>x1>>yy1>>x2>>y2>>x3>>y3){		if(x1==0&&yy1==0&&x2==0&&y2==0&&x3==0&&y3==0) break;		double A=0.5 * abs((x1 - x3)*(y2 - yy1) - (x1 - x2)*(y3 - yy1));		int k; int tmp=0;		if(x1==x2)		tmp+=(max(y2,yy1)-min(y2,yy1)+1);		else {			k=max(x1,x2);			for(int i=min(x1,x2);i<=k;i++){				if(((yy1-y2)*(i-x2))%(x1-x2)==0)				tmp++;			}		}		if(x1==x3)		tmp+=(max(yy1,y3)-min(yy1,y3)+1);		else{			k=max(x1,x3);			for(int i=min(x1,x3);i<=k;i++){				if(((yy1-y3)*(i-x3))%(x1-x3)==0)				tmp++;			}		}		if(x2==x3)		tmp+=(max(y2,y3)-min(y2,y3)+1);		else{			k=max(x2,x3);			for(int i=min(x2,x3);i<=k;i++){				if(((y2-y3)*(i-x3))%(x2-x3)==0)				tmp++;			}		}		tmp-=3;		int ans=((A+1)*2-tmp)/2;		cout<<ans<<endl;	}	return 0;}