作者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