描述

給定一個nxm的網(wǎng)格, 請計算三點都在格點上的三角形共有多少個.

---

分析

• 三角形的三個頂點不能共線. 這是入手點.
• 下面來考慮一個問題, 原點到點(x,y)之間的線段上有幾個整點
  
  • 如果把x, y同除以一個數(shù)g保證結(jié)果是整數(shù), 那么(x/g, y/g)一定是原點到(x,y)的線段上的整點
  • 原點到(x,y)的線段上的整點中 每兩個相鄰的之間的距離相等. 而且等于原點到第一個點的距離.
  • 那么找到第一個點就可以知道共有幾個了. 比如第一個點(x0,y0). 那么一共x/x0個點.
  • 第一個點, 也就是橫縱坐標(biāo)最小的, 就是g最大的. g最大是gcd(x,y). 第一個點的橫坐標(biāo)就是x/gcd(x,y). 帶到上面一共gcd(x,y)個整點. 這些點中包含了(x,y).
• 如果不考慮三點共線的情況, 共tot = (m+1)*(n+1)個點, 一共的方案數(shù)是C(tot, 3)種.
• 然后就可以枚舉從原點出發(fā)的向量(x,y), 用gcd算出原點到點(x,y)之間的線段上有幾個整點. 然后計算有幾個等于(x,y)的向量. 相乘.

---

代碼

https://code.csdn.net/snippets/621864

總結(jié)

以上是生活随笔為你收集整理的BZOJ-3505-数三角形-CQOI2014的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。