usaco_3_4_3_fence9_皮克定理求多边形中的点的个数.cpp

usaco自己做的1到5章的代码

/*
PROB: fence9
LANG: C++
*/
/*
这道题嘛，用到一个很牛B的定理：皮克定理。
给定顶点座标均是整点（或正方形格点）的简单多边形，皮克定理说明了其面积A和内部格点数目i、边上格点数目b的关系：A = i + b/2 - 1。
另外，由于要统计边上的整数点，又用到另一个结论：斜边上的整数点等于斜边顶点差的最大公约数。如A(x1,y1),B(x2,y2)，那么AB上的整数点就为gcd(abs(x1-x2),abs(y1-y2))-1（这个不包含A，B两点）。这样，算面积用海伦公式：
周长一半:s=(a+b+c)/2
面积：S=sqrt(s*(s-a)*(s-b)*(s-c));
这样就得到三角形内的点数：p=S-k/2+1;
*/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<fstream>
#define MAX 2001
using namespace std;
ifstream fin("fence9.in");
ofstream fout("fence9.out");
int __gcd(int a,int b)
{
	if(a<b) swap(a,b);
	while(b!=0)
	{
		int t=b;
		b=a%b;
		a=t;
	}
	return a;
}
double Len(int x1,int y1,int x2,int y2)
{
	return sqrt((x1-x2)*(x1-x2)*1.0+(y1-y2)*(y1-y2));
}
int main()
{
	int i,j,k,n,m,p;
	double a,b,c,S,s;
	fin>>n>>m>>p;
	i=__gcd(n,m);
	j=__gcd(abs(n-p),m);
	k=i+j+p;
	a=Len(n,m,p,0);
	b=Len(0,0,n,m);
	c=Len(0,0,p,0);
	s=(a+b+c)/2;
	S=sqrt(s*(s-a)*(s-b)*(s-c));
	i=int(S+0.5)-k/2.0+1;
	fout<<i<<endl;
	return 0;
}