首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。