Tag很好心的給你math的提示,
查一下就能找到
關鍵字「皮克定理」
老實說這種東西我根本不想知道
其還有一題完整的(多邊形格子點),
但我懶得寫,感覺三角形就夠麻煩了
多邊形更麻煩的是你要判斷哪兩的點是相連的,
三角形則不用,每兩點必互相相連嘛~~
如果你有去查了,
你應該會得到一個公式 : i=A+1+b/2
i : 內部格子點含邊上的總數
A : 該多邊形面積
b : 該多邊形邊上的格子點數目
i當然就是我們要的,那A和b怎麼求呢...
恩...如果你聽過鞋帶公式,那可以直接將座標轉換成面積,
若沒有,也是可以用其他像海龍公式之類的,
反正都給你三個點的座標了,總有辦法的
接著就是比較麻煩的地方了...(其實也還好
計算邊上的格子點數
如果你寫過TOJ20了,那你可能會知道怎麼辦
如果沒有,那你則可以先寫TOJ20
另外依照我的AC程式結果
當三點連成一線的退化三角形,正解應該是線上格子點而非0
281.cpp(有點小疑惑但還是正解