来学习下pick定理。这道题是入门题。
题意就是给你一个多边形，让你求出多边形内部的点和边上的点，还有多边形的面积。
先说pick定理，就是计算点阵中顶点在点上的多边形的面积，假设a表示内部的点数，b表示边界上的点数，s表示面积，那么2*s=(2*a+b-2)。
然后我们发现这道题纯粹就是用pick定理，但是得求得a,b才能求出面积s。
然后利用三角形相似可以求出一个线段上整点的个数，但是没有办法求出内部的点。但是面积可以用叉积求得，所以这个题得先求s，b，在求出a。
再说如何求线段上整点的个数：我之前看到的是线段两个端点坐标做差求gcd再+1就是线段上整点的个数，这个题解直接把输入的点的坐标求下gcd就完成了。可能是哪个定理吧，暂时没有证明的能力QAQ。
再说求叉积，这个题求叉积我也是第一次见，还是应用了一个定理，我还是没见过QAQ。就是把输入的点坐标先加上前一个点的坐标再叉积，然后就OK了。。。
#include <iostream> #include <cmath> #include <vector> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; #define gcd(a,b) __gcd(a,b) const int maxn=130; struct node { int x,y; }pp[maxn]; int n,t; int Area(node a,node b) { return a.x*b.y-a.y*b.x; } int main() { pp[0].x=0; pp[0].y=0; scanf("%d",&t); for(int l=1;l<=t;l++) { int S=0,b=0,dx,dy; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&pp[i].x,&pp[i].y); dx=pp[i].x; if(dx<0) dx=-dx; dy=pp[i].y; if(dy<0) dy=-dy; b+=gcd(dx,dy); pp[i].x+=pp[i-1].x; pp[i].y+=pp[i-1].y; S+=Area(pp[i],pp[i-1]); } if(S<0) S=-S; printf("Scenario #%d:\n",l); printf("%d %d %.1f\n\n",(S-b+2)/2,b,S*0.5); } return 0; }