UVa 10088 - Trees on My Island （pick定理）

样例：

输入：
12
3 1
6 3
9 2
8 4
9 6
9 9
8 9
6 5
5 8
4 4
3 5
1 3
12
1000 1000
2000 1000
4000 2000
6000 1000
8000 3000
8000 8000
7000 8000
5000 4000
4000 5000
3000 4000
3000 5000
1000 3000
4
0 0
1000000 0
1000000 1000000
0 1000000
4
0 0
100 0
100 100
0 100

输出：

25990001

999998000001

9801

分析：Pick定理：一个计算点阵中顶点在格点上的多边形面积公式：S=a+b/2.0-1，其中a表示多边形内部的点数，b表示多边形边界上的点数，s表示多边形的面积。

首先利用叉积求多边形的面积S；

然后求出b，方法是枚举每条边，然后以改边构成一个直角三角形，直角边长度是n，m，斜边上有的整数点的个数是gcd（n，m）-1（不包括两端点）最后b=b+n;

即可

最后a=S+1-b/2.0;

需要注意的地方是：a可能爆int

 #include"stdio.h"

 #include"string.h"

 #include"algorithm"

 #include"stdlib.h"

 #include"math.h"

 #include"map"

 #include"queue"

 #include"iostream"

 #define M 1009

 #define inf 0x3f3f3f3f

 #define eps 1e-9

 using namespace std;

 struct node

 {

     double x,y;

     node(){}

     node(double x,double y)

     {

         this->x=x;

         this->y=y;

     }

     node operator-(node a)

     {

         return node(x-a.x,y-a.y);

     }

     node operator+(node a)

     {

         return node(x+a.x,y+a.y);

     }

     double operator*(node a)

     {

         return x*a.x+y*a.y;

     }

     double operator^(node a)

     {

         return x*a.y-y*a.x;

     }

 }p[M];

 double len(node a)

 {

     return sqrt(a*a);

 }

 double dis(node a,node b)

 {

     return len(b-a);

 }

 double cross(node a,node b,node c)

 {

     return (b-a)^(c-a);

 }

 int gcd(int a,int b)

 {

     return b==?a:gcd(b,a%b);

 }

 int point(node a,node b)

 {

     int m=(int)(fabs(b.x-a.x)+0.5);

     int n=(int)(fabs(b.y-a.y)+0.5);

     int r=gcd(m,n);

     return r-;

 }

 int main()

 {

     int n;

     while(scanf("%d",&n),n)

     {

         for(int i=;i<n;i++)

             scanf("%lf%lf",&p[i].x,&p[i].y);

         double sum=;

         node O(,);

         double num=n;

         for(int i=;i<n;i++)

         {

             num+=point(p[i],p[(i+)%n]);

             sum+=cross(O,p[i],p[(i+)%n]);

         }

         sum=fabs(sum)/2.0;

         double ans=sum+-0.5*num;

         printf("%.0f\n",ans+0.001);

     }

     return ;

 }

 /*

 12

 3 1

 6 3

 9 2

 8 4

 9 6

 9 9

 8 9

 6 5

 5 8

 4 4

 3 5

 1 3

 12

 1000 1000

 2000 1000

 4000 2000

 6000 1000

 8000 3000

 8000 8000

 7000 8000

 5000 4000

 4000 5000

 3000 4000

 3000 5000

 1000 3000

 4

 0 0

 1000000 0

 1000000 1000000

 0 1000000

 4

 0 0

 100 0

 100 100

 0 100

 */

巴特西

UVa 10088 - Trees on My Island （pick定理）

最新文章

热门文章