P 國女王要出席重要典禮,她的護衛團決定在她周圍形成防護網,讓女王身處在護衛群的深處。護衛隊長煩惱了很久,在護衛們都站定位的狀況下,他不知該如何判斷哪個位置是所謂的「深處」。護衛隊長求教於女王身邊的大臣,一位聰明的大臣「圖基」思索多日後,將他的發現告訴了護衛隊長。
圖基用上面的圖例解釋給護衛隊長聽;圖中的圓點代表護衛們的位置:
1. 首先,任意選取一條直線將護衛們均分為人數均等的 A 與 B 兩群,如圖 (一)。
2. 慢慢改變這條線的斜率,保持 A 與 B 的分群不變,直到該線碰到 A 中的某護衛與 B 群中的某護衛為止,如圖(二);注意因為可沿順時針或逆時針方向改變直線的斜率,所以恰有兩條可能的線。
3. 步驟 2 所找到二線的交點,極有可能是所求的「深處」,如圖(三) 之p。
圖基的話還沒說完,護衛隊長就拿著三張圖跑了出去,將圖丟給了王國的程式設計師,並告訴他所有護衛的平面坐標,請他參考圖例寫程式計算「深處」位置。
王國的程式設計師拿到三張圖與護衛們的座標後,直接依 x 坐標將護衛們分為同等人數的兩半 (x 坐標較小的為一群,x 坐標較大的為另一群),然後再求出上述步驟 3 的交點。聰明的你應會發現,步驟 1 的均分直線選的不同的話,步驟 3 所求出的交點也可能不同,而這樣的狀況就沒有所謂的深處;然而圖基來不及提醒護衛隊長這件事,王國的程式設計師自然也不會知道了。
請寫一支程式,重現王國的程式設計師的計算結果。
第一行有一正偶數 $n$,代表護衛人數;接下來的 $n$ 行,每行有兩個整數,分別表示一護衛在平面上的 $x$ 與 $y$ 座標,此二整數以一空白分隔。護衛的 $x$ 座標均不相同。另可確定的是,護衛人數分為兩群後,每一群護衛皆有三人不共線的特性。
輸出 $2$ 個數字,以一空白分隔,表示王國的程式設計師計算出的「深處」之 $x$ 與 $y$ 座標;兩數字皆須四捨五入至小數點後二位。
評分說明
本題共有三組測試資料,每組可有多筆測試資料:
第一組測試資料,$6 \leq n \leq 3000$,共 25 分。
第二組測試資料,$20000 \leq n \leq 50000$,且以 x 坐標大小區分出的 A 與 B 兩群點,各自凸包 (convex hull) 上的頂點數不超過 $3000$,共 40 分。
第三組測試資料,$60000 \leq n \leq 100000$,共 35 分。
註:原題未標明座標範圍,這裡的測資保證所有數字絕對值小於$10^ 9$
107北市賽
testdata set by Omelet
註:因為測資好難生所以多設了一些dependency
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~19 | $6 \leq n \leq 3000$ | 25 |
2 | 0~29 | $20000 \leq n \leq 50000$,且以 x 坐標大小區分出的 A 與 B 兩群點,各自凸包 (convex hull) 上的頂點數不超過 $3000$ | 40 |
3 | 0~39 | $60000 \leq n \leq 100000$ | 35 |