?? usaco_3_4_3_fence9_皮克定理求多邊形中的點的個數.cpp
字號:
/*
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;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -