f990. 距離 - 高中生程式解題系統

內容

有一天小 C 正在算數學，遇到一個題目：有兩個點 $(0, 1)$ 和 $(2, 3)$ ，要在 $x$ 軸上取一個點，要取哪一點到兩個點的距離和會最小呢？

正當小 C 想不出來時，小 B 告訴他了解法，原來只要把 $(2, 3)$ 對稱到 $(2, - 3)$ ，再把 $(0, 1)$ 跟 $(2, - 3)$ 連線，跟 $x$ 軸的交點就是答案了，所以答案是 $(0.5, 0)$ 。

小 C 又問了下一題，有 $n$ 個點在平面上，有一條直線 $y = m x + k$ ，要在這條線上取一點，而且這點到其他 $n$ 個點的距離和最小，請問這點的 $x$ 座標值？

這就難倒小 B 了，於是他請求你的幫助。

輸入說明

第一行有一個數字 $t$ ，代表有幾組測試資料。

每組測試資料第一行有三個整數 $n, m, k$ ，代表平面上有 $n$ 個點，和直線為 $y = m x + k$ 。

接下來 $n$ 行，每行有兩個整數 $x_{i}, y_{i}$ ，代表 $n$ 個點的座標值。

輸出說明

每筆測試資料輸出 $x_{a n s}$ ，代表答案的 $x$ 座標。

令 $f (x)$ 代表用這個 $x$ 值代入，與 $n$ 個點的距離和。

只要用 $x_{a n s}$ 算出的 $f (x_{a n s})$ 與標準輸出檔裡的 $x_{a c}$ 算出的 $f (x_{a c})$ ，滿足 $| f (x_{a c}) - f (x_{a n s}) | \leq 1$ ，就算通過。

格式不限，只要可以正常運作就好了。

範例輸入 #1

範例輸出 #1

0.499991234567

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (50%): 3.0s , <10M
公開測資點#1 (50%): 3.0s , <10M

提示：

標籤:

三分搜二分搜數學

出處:

第五屆簡單的小競賽 [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
29148	fire5386 (becaidorz)	f990	Tenary Search	611	2022-02-01 20:15