?

Area

?

题目大意：给出每个点相对于前一个点的坐标增量，增量都是整数，会得到一个在网格上多边形，求多边形内的格点、多边形上的格点以及多边形的面积。

?

解题思路：这个题主要是Pick定理的应用（Pick定理传送门），另外还有几个其他的知识点。

Pick定理：平面上以格子点为顶点的简单多边形的面积=边上的点数/2+内部的点数+1。

计算多边形边上的格点数目：Σ ( GCD ( abs(dx), abs(dy)) ) dx是每个点相对于前一个点的x的增量， dy是每个点相对于前一个点的y的增量。

?

代码如下：

?

#include 
  
   
#include 
   
     #include 
    
      struct Point { int x, y; } P[105]; int gcd(int a, int b){ return b?gcd(b, a%b):a; } int main() { int n; int x, y; int T, icase = 1; scanf(%d, &T); while(T--) { scanf(%d, &n); double area = 0; int sum = 0; P[0].x = P[0].y = 0; for(int i = 1; i <= n; ++i) { scanf(%d%d, &x, &y); P[i].x = P[i-1].x+x; P[i].y = P[i-1].y+y; area += P[i].x*P[i-1].y-P[i].y*P[i-1].x; sum += gcd(abs(x), abs(y)); } area = fabs(area*0.5); printf(Scenario #%d: , icase++); printf(%.0lf %d %.1lf , (area*2-sum+2)/2, sum, area); } return 0; } 
    
   
  

?

?

?