Re: [問題] Google Code Jam 2008, EMEA Semifinal-A
※ 引述《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
推
04/01 19:03, , 1F
04/01 19:03, 1F
推
04/01 19:38, , 2F
04/01 19:38, 2F
推
06/14 14:14, , 3F
06/14 14:14, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 3 篇)：