作者LPH66 (-858993460)
看板Prob_Solve
標題Re: [問題] Google Code Jam 2008, EMEA Semifinal-A
時間Sun Apr 1 18:53:13 2012
※ 引述《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
1F：推 DJWS:剛剛也在思考這題 看了你的解法才發現自己誤會題意了... XD 04/01 19:03
2F：推 RockLee:感謝 L 大的說明, L 大真是學識淵博 <_.._> 04/01 19:38
3F：推 amos6064:感謝L大說明 06/14 14:14