題目傳送門

刷USACO偶然遇到的，可能是人生中第一道正兒八經的計算幾何。

題目大意：在平面直角坐標系中給你一個以格點為頂點的三角形，求三角形中的整點個數。

因為必修5和必修2的陰影很快就想到了數學中的線性規劃，求出兩條直線的方程，然后枚舉所有整點看是否滿足條件。結果莫名其妙的掛掉了，樣例過不了。

既然是計算幾何萌新，那就看一看題解吧。

正解是一個定理-Pick定理，內容如下

　　“Pick定理是說，在一個平面直角坐標系內，如果一個多邊形的頂點全都在格點上，那么這個圖形的面積恰好就等于邊界上經過的格點數的一半加上內部所含格點數再減一。”--Matrix67，侵刪。

于是我們就愉快地O（1）算出來了。

Code

1 #include<cmath> 2 #include<cstdio> 3 4 using namespace std; 5 6 int n,m,p,b,S,ans; 7 8 int gcd(int x,int y) 9 { 10 return y ? gcd(y , x%y) : x ; 11 } 12 13 int main() 14 { 15 scanf("%d%d%d",&n,&m,&p); 16 b=gcd(n,m)+gcd(fabs(n-p),m)+p; 17 S=(p*m)>>1;ans=S+1-(b>>1); 18 printf("%d",ans); 19 return 0; 20 } View Code

?

轉載于:https://www.cnblogs.com/nopartyfoucaodong/p/9531098.html

總結

以上是生活随笔為你收集整理的Luogu P2735 电网【真·计算几何/Pick定理】By cellur925的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。