題目連結:
題目大意:
給定一正整數 N (N ≦ 3, 000),代表有 N 條邊。接著的一列有 N 個正整數(大小皆在 2 ^ 30 以內),代表這 N 條邊的長度。
求從這 N 條邊取三條,可以組出多少種相異的直角三角形?
因為題目是問「直角」三角形,而不是一般的三角形。因此,我們可以窮舉出兩條邊的取法,並得出以這兩條邊作為股的直角三角形之斜邊長應為何。
然後,得到了這個斜邊長之後可以先檢查其是否為整數(可以在計算前判斷,計算後也可以)。若為整數的話,再判斷在這 n 條邊有無長度相符的;若有的話,即得到了一組直角三角形。
為了方便判斷斜邊長有無在 n 條邊裡,我們可以先將其進行排序(由小到大排)。接著只要窮舉兩股,找出斜邊長。並計算出在其當中有出現過幾個合理的直角三角形即可。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。