PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Google Code Jam 2008, EMEA Semifinal-A

看板Prob_Solve (計算數學 Problem Solving)作者LPH66 (-858993460)時間12年前 (2012/04/01 18:53)推噓3(3推 0噓 0→)

留言3則, 3人參與討論串2/3 (看更多)

※ 引述《RockLee (Now of all times)》之銘言： <43> : long xn = x1[0]; : long yn = y1[0]; : long axn = x1[1] - x1[0]; : long ayn = y1[1] - y1[0]; : long bxn = x1[2] - x1[0]; : long byn = y1[2] - y1[0]; : long xm = x2[0]; : long ym = y2[0]; : long axm = x2[1] - x2[0]; : long aym = y2[1] - y2[0]; : long bxm = x2[2] - x2[0]; : long bym = y2[2] - y2[0]; 這裡是把輸入轉化成頂點一 (xn,yn) 和由頂點射出的兩邊向量 (axn,ayn) (bxn,byn) (xm,ym) (axm,aym) (bxm,bym) : long a = axn - axm; : long b = bxn - bxm; : long c = xm - xn; : long d = ayn - aym; : long e = byn - bym; : long f = ym - yn; : double p = 0.0; : double q = 0.0; : if (a * e != b * d) : { : p = (1.0 * c * e - b * f) / (1.0 * a * e - b * d); : q = (1.0 * a * f - c * d) / (1.0 * a * e - b * d); : } 他的想法是這樣的: 這個不動點的座標 (x,y) 一定存在兩個實數 p, q 滿足 (x,y) = (xn,yn) + p (axn,ayn) + q(bxn,byn) = (xm,ym) + p (axm,aym) + q(bxm,bym) 因此他去解後面這個聯立方程移項後可以發現方程變成了 (axn - axm) p + (bxn - bxm) q = xm - xn (ayn - aym) p + (byn - bym) q = ym - yn 這係數是不是在哪看過呢? 沒錯, 他把這六個係數放進 a ~ f 裡去了也就是這個方程變成了這樣: a*p + b*q = c d*p + e*q = f 於是 if 裡面就是當這方程有唯一解時去把它解出來如果不是唯一解時 (也就是 a*e - b*d == 0 時) 因為不會無解 (這是數學定理, 有興趣的話可以搜尋「巴拿赫不動點定理」) 所以一定是無窮多解這只可能是兩個三角形一樣大且疊在一樣的位置所以就任選 p = 0, q = 0 來輸出了 : pw.printf("%.6f %.6f\n", xn + p * axn + q * bxn, yn + p * ayn + q * byn); : } : } -- LPH [acronym] = Let Program Heal us -- New Uncyclopedian Dictionary, Minmei Publishing Co. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.28.92