※ 引述《pinglunliao (王者：一條孤獨的不歸路)》之銘言： : 原題目：　http://www.cs.ualberta.ca/~contest/club/020208/00209.html : 某個參考解答　http://www.cs.ualberta.ca/~contest/club/020208/00209code1.html : 我對這個參考解答的底下部分有疑問：「他是怎麼推出公式來的？」 : p[psize].n = pset[i]; : x = sqrt(2*pset[i])-1; : while(1){ : if(x*(x-1)/2 < pset[i] && pset[i] <= x*(x+1)/2) break; : x++; : } : p[psize].x = x; : p[psize].y = pset[i]-x*(x-1)/2; : p[psize].z = x*(x+1)/2+1 - pset[i]; : 版友們對　Triangular Vertices　有別的解法嗎？ 我的想法是把點看成這樣： 　Ｙ 　↑ 　︴ 　｜＼｜＼｜＼｜＼｜ ４15－20－26－33－41－ 　｜＼｜＼｜＼｜＼｜＼ ３10－14－19－25－32－ 　｜＼｜＼｜＼｜＼｜＼ ２６－９－13－18－24－ 　｜＼｜＼｜＼｜＼｜＼ １３－５－８－12－17－ 　｜＼｜＼｜＼｜＼｜＼ ０１－２－４－７－11－…→Ｘ 　０　１　２　３　４ 然後去找出每個點對應的x,y座標 檢查兩點是否連線就變成它們的x,y座標X相同或Y相同或X+Y相同 距離則為(X相同時)Y的差或(Y相同時)X的差或(X+Y相同時)X的差 然後因為題目給的點順序不一定 所以要每對之間都檢查 (點最多才6個 所以這一定OK) 確定邊之後再檢查是否能連成三角形/平行四邊形/六邊形 距離是否相等 等等 (可以就直接做成一個小graph來檢查) 上面的式子 裡面的x就是我的X+Y+1 裡面的y就是我的Y+1 裡面的z就是我的X ＿ 那個√2n-1只是要找出的X+Y+1的值的下界估計而已 (這樣while只需要跑個幾圈就找到x了 如果不先估計 while可能會跑非常多圈) -- 就我的印象中 92年全國高中資訊能力競賽決賽的題目之一和這題非常像 當時的題目是直接把圖形給成上面那樣 (只差沒有畫出座標軸而已) 然後也沒有限定距離要相等 只要求有邊連得起來即可 -- **** 說: 不要期望一個精神力差不多已經見底的人阿Orz --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 192.192.197.115