Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

PKU 1265 Area---计算几何

Posted on 2009-10-02 03:01 Uriel 阅读(196) 评论(0)  编辑 收藏 引用 所属分类: POJ计算几何

求顶点为整数的任意多边形内部整点数(Pick定理),边上整点数(GCD),面积(叉积)

第一次知道Pick定理。。
注意。。叉积求出面积可能是负数,需要处理下
/*Problem: 1265  User: Uriel 
   Memory: 172K  Time: 16MS 
   Language: C++  Result: Accepted
*/


#include
<math.h>
#include
<stdio.h>
#include
<stdlib.h>
#define MAXN 110
#define ABS(x) (x<0?-x:x)
struct point
{
    
int x,y;    
}
;

point P[MAXN],T;

int t,n,i,EPoint,IPoint,Asum;

int cross_product(point a,point b)
{
    
return a.x*b.y-a.y*b.x;
}


int GCD(int x,int y)
{
    
if(y==0)return x;
    
else
        
return GCD(y,x%y);
}


int main()
{
    scanf(
"%d",&t);
    
for(int i=1;i<=t;i++)
    
{
        scanf(
"%d",&n);
        Asum
=0;
        EPoint
=0;
        P[
0].x=0;
        P[
0].y=0;
        
for(int j=1;j<=n;j++)
        
{
            scanf(
"%d %d",&T.x,&T.y);
            P[j].x
=P[j-1].x+T.x;
            P[j].y
=P[j-1].y+T.y;
            EPoint
+=GCD(ABS(T.x),ABS(T.y));
            Asum
+=cross_product(P[j-1],P[j]);
        }

        
if(Asum<0)
        
{
            Asum
=-Asum;
        }

        IPoint
=Asum/2+1-EPoint/2;
        printf(
"Scenario #%d:\n%d %d %.1f\n\n",i,IPoint,EPoint,((double)Asum)/2);
    }

//    system("PAUSE");
    return 0;
}


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