Re: [問題] Triangular Vertices
※ 引述《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
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：