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