2018年6月12日 星期二

TOJ281

Tag很好心的給你math的提示,
查一下就能找到

關鍵字「皮克定理」


老實說這種東西我根本不想知道

其還有一題完整的(多邊形格子點),
但我懶得寫,感覺三角形就夠麻煩了
多邊形更麻煩的是你要判斷哪兩的點是相連的,
三角形則不用,每兩點必互相相連嘛~~

如果你有去查了,

你應該會得到一個公式 : i=A+1+b/2
i : 內部格子點含邊上的總數
A : 該多邊形面積
b : 該多邊形邊上的格子點數目

i當然就是我們要的,那A和b怎麼求呢...

恩...如果你聽過鞋帶公式,那可以直接將座標轉換成面積,
若沒有,也是可以用其他像海龍公式之類的,
反正都給你三個點的座標了,總有辦法的

接著就是比較麻煩的地方了...(其實也還好

計算邊上的格子點數
如果你寫過TOJ20了,那你可能會知道怎麼辦
如果沒有,那你則可以先寫TOJ20

另外依照我的AC程式結果
當三點連成一線的退化三角形,正解應該是線上格子點而非0


281.cpp(有點小疑惑但還是正解