首页 > 代码库 > hdu 1705 Count the grid(皮克定理)

hdu 1705 Count the grid(皮克定理)

2024-09-06 22:19:18   217人阅读

题目链接：hdu 1705 Count the grid

题意：

给定一个三角形三点坐标，问三角形内有多少个坐标均为整数的点。

题解：

给定顶点坐标均是整点（或正方形格点）的简单多边形，皮克定理说明了其面积 S 和内部
格点数目 n、边上格点数目 s 的关系：S = n +s/2+1

三角形两向量叉积/2=面积。

向量上整数点数为gcd（v.x,v.y）（此公式对于一条边上的结果不准确，但是三条边加在一起的和是准确的）

技术分享 
 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4 
 5 struct point
 6 {
 7     int x,y;
 8     point(){}
 9     point(int _x,int _y):x(_x),y(_y){}
10     point operator -(point b){return point(x-b.x,y-b.y);}
11 }p[3];
12 
13 int cross(point a,point b){return a.x*b.y-b.x*a.y;}
14 
15 int main()
16 {
17     while(~scanf("%d%d%d%d%d%d",&p[0].x,&p[0].y,&p[1].x,&p[1].y,&p[2].x,&p[2].y))
18     {
19         if(!p[0].x&&!p[0].y&&!p[1].x&&!p[1].y&&!p[2].x&&!p[2].y)break;
20         int tmp=0;
21         F(i,0,2)
22         {
23             point t=p[(i+1)%3]-p[i];
24             tmp+=__gcd(abs(t.x),abs(t.y));
25         }
26         int s=abs(cross(p[2]-p[0],p[1]-p[0]));
27         printf("%d\n",(s-tmp+2)/2);
28     }
29     return 0;
30 }
View Code

 

hdu 1705 Count the grid(皮克定理)


联系
我们