皮克定理说明了其面积S和内部格点数目a、边上格点数目b的关系：S = a + b/2 - 1。
根据三角形面积公式求出S。
如果知道了b，那么三角形内部格点数目a也就求出来了。
可以证明，一条直线((0,0),(n,m))上的格点数等于n与m的最大公约数+1。即b=gcd(n,m)+1. gcd(n,m)为n与m的最大公约数。
/**//*
ID: lorelei3
TASK: fence9
LANG: C++
*/
#include <fstream>
#include <cmath>
#include <iostream>
using namespace std;
int m,n,p;
int gcd(int a, int b)
{
if(b==0) return a;
else return gcd(b, a%b);
}
int main(){
int S, a, b=0;
ifstream fin("fence9.in");
ofstream fout("fence9.out");
fin>>n>>m>>p;
b += gcd(n,m);
b += gcd(abs(n-p),m);
b += p;
S = (p*m)/2;
//S = a + b/2 - 1;
a = S+1-b/2;
fout<<a<<endl;
return 0;
}代入皮克公式，即可求出a的值
posted on 2011-01-19 19:04
小阮 阅读(250)
评论(0) 编辑 收藏 引用 所属分类:
USACO