切換
舊版
前往
大廳
主題

ZeroJudge - d408: 我要最小值 (Part 2) 解題心得

Not In My Back Yard | 2018-12-12 12:43:08 | 巴幣 0 | 人氣 129

題目連結:


題目大意:
給定一個正整數 N (1 ≦ N ≦ 5,000),代表接下來有 N 列的測試資料(但是 N 列完可能會有下一個 N 值,當 N = 0 時,停止程式)。

每一列會有三個正整數 a、b、c (1 ≦ a 、 b 、 c ≦ 1,000 ),保證可以形成一三角形 ABC 。

現想在每一個三角形 ABC 裡找到一點 P ,使得
(PA 邊)^ 2 + (PB 邊) ^ 2 + (PC 邊) ^ 2
有最小值。求最小值,輸出此值並四捨五入到小數點後第一位。



範例輸入:
1
1 1 1
2
4 4 4
5 5 5
0


範例輸出:
1.0
16.0
25.0



解題思維:
首先,我們將給定的 a、b、c 三邊的對角頂點分別命名為 A、B、C ,並放置於一座標平面軸。則三點 A、B、C 之座標設為如下圖所示:
而其中的 cos C 之值可由餘弦公式求出:
而 sin C 也便可以得知:


設點 P 的座標 X、Y ,則題目的式子可改寫為(根據距離公式):
之後,各自把式子展開,分別最小化 x 、 y 。便得到最小值為以下:

將值代入以上式子,求出來的值便是題目所求。


此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作