随笔-20  评论-16  文章-36  trackbacks-0
      这道题目用了蛮多结论的,要求格子面上多边形的边上点数,内部点数和占的面积,用到的结论:
      1.以格子点为顶点的线段,覆盖的点的个数为GCD(dx,dy),其中,dxdy分别为线段横向占的点数和纵向占的点数。如果dx或dy为0,则覆盖的点数为dy或dx。
      2.Pick公式:平面上以格子点为顶点的简单多边形,如果边上的点数为on,内部的点数为in,则它的面积为A=on/2+in-1。(
http://episte.math.ntu.edu.tw/articles/sm/sm_25_10_1/index.html有证明和推导)
      3.任意一个多边形的面积等于按顺序求相邻两个点与原点组成的向量的叉积之和(黑书上有说明)
      下面是我的实现代码:
#include <iostream>
using namespace std;

int Gcd( int a, int b ){    //a, b为两个输入的数,返回最大公约数
    while( b!= 0 ){
        
int r= b;
        b
= a % b;
        a
= r;
    }

    
return a;
}

int main(){
    
int i, k, t, n, x[101], y[101], dx, dy, on, in, area;
    scanf(
"%d",&t);
    
for( k= 1; k<= t; k++ ){
        scanf(
"%d",&n);
        
for( i= 1, on=area=x[0]=y[0]= 0; i<= n; i++ ){
            scanf(
"%d%d",&dx,&dy);
            x[i]
= dx+ x[i-1];
            y[i]
= dy+ y[i-1];
            on
+= Gcd(abs(dx),abs(dy));
            area
+= x[i-1]*y[i]-x[i]*y[i-1];
        }

        
in= ( area- on+ 2 )/ 2;
        printf(
"Scenario #%d:\n%d %d %.1lf\n\n",k,in,on,area/2.0);
    }

    
return 0;
}

posted on 2009-06-26 18:26 古月残辉 阅读(779) 评论(1)  编辑 收藏 引用 所属分类: 计算几何

评论:
# re: POJ 1265 Area 2010-03-22 14:11 | 祝你好运
博主你好,我刚刚仰慕了一下您的poj1265的代码,我想知道结论1的证明,您有吗?可以mail我675313675@qq.com,先谢谢了!  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理