POJ 3711 - Mayan Pyramid

http://poj.org/problem?id=3711

概要

平面上の三点 A, B, C の座標と h が与えられ，底面が三角形 ABC で高さが h の四面体 ABCP を作る．

P から AB, BC, CD への垂線の足をそれぞれ D, E, F としたとき，PD^2 + PE^2 + PF^2 が最小になるように点 P の座標を決定する． このとき，P を平面 ABC に射影した点 Q の座標を答える．

制約

• 座標の値および高さ < 1000
• 出力は 10^-2 の精度

解法

まず

• PD^2 = PQ^2 + DQ^2
• PE^2 = PQ^2 + EQ^2
• PF^2 = PQ^2 + FQ^2

より，PD^2 + PE^2 + PF^2 を最小にすることは DQ^2 + EQ^2 + FQ^2 を最小にすることと同値．

コーシー・シュワルツの不等式から (DQ^2 + EQ^2 + FQ^2)*(AB^2 + BC^2 + CA^2) >= (DQ*AB + EQ*BC + FQ*CA)^2 であり， 三角形 ABC の面積を S とすると右辺 = (2*S)^2 であるため，DQ^2 + EQ^2 + FQ^2 の最小値は (2*S)^2/(AB^2 + BC^2 + CA^2) という定数で与えられる．

等号成立は DQ/AB = EQ/BC = FQ/CA のとき．つまり，DQ : EQ : FQ = AB : BC : CA となるときである． このときの Q の座標は，Q は角 C を AB : BC に分ける直線上にあり，かつ角 A を CA : AB に分ける直線上にあることから求めることができる．

ちなみにこのような点 Q は Lemoine 点と呼ばれているらしい． http://kikagaku.at-ninja.jp/trianglegeometry/Lemoinepoint.html

 1 #include <cstdio>
 2 #include <complex>
 3 using namespace std;
 4 typedef complex<double> P;
 5 
 6 inline double cross(const P& a, const P& b) { return a.real()*b.imag() - b.real()*a.imag(); }
 7 struct line/*{{{*/
 8 {
 9   P a, b;
10   line() {}
11   line(const P& p, const P& q) : a(p), b(q) {}
12 
13   inline P intersection(const line& ln) const
14   {
15     // assert(intersects(ln))
16     const P x = b - a;
17     const P y = ln.b - ln.a;
18     return a + x*(cross(y, ln.a - a))/cross(y, x);
19   }
20 };/*}}}*/
21 
22 P sector(const P& a, const P& b)
23 {
24   const double x = abs(a), y = abs(b);
25   return a/x*y + b/y*x;
26 }
27 
28 int main()
29 {
30   double ax, ay, bx, by, cx, cy, h;
31   while (scanf("%lf %lf %lf %lf %lf %lf %lf", &ax, &ay, &bx, &by, &cx, &cy, &h) != EOF) {
32     const P a(ax, ay), b(bx, by), c(cx, cy);
33     const line l(c, c + sector(b-c, a-c));
34     const line m(a, a + sector(c-a, b-a));
35     const P p = l.intersection(m);
36     printf("%.2f %.2f\n", p.real(), p.imag());
37   }
38   return 0;
39 }