TopCoder

FHVirus
$\Huge 8e7 二分圖判斷範例程式碼有錯,道歉!$

User's AC Ratio

40.0% (2/5)

Submission's AC Ratio

18.2% (2/11)

Tags

Description

P 國女王要出席重要典禮,她的護衛團決定在她周圍形成防護網,讓女王身處在護衛群的深處。護衛隊長煩惱了很久,在護衛們都站定位的狀況下,他不知該如何判斷哪個位置是所謂的「深處」。護衛隊長求教於女王身邊的大臣,一位聰明的大臣「圖基」思索多日後,將他的發現告訴了護衛隊長。

圖基用上面的圖例解釋給護衛隊長聽;圖中的圓點代表護衛們的位置:
1. 首先,任意選取一條直線將護衛們均分為人數均等的 A 與 B 兩群,如圖 (一)。
2. 慢慢改變這條線的斜率,保持 A 與 B 的分群不變,直到該線碰到 A 中的某護衛與 B 群中的某護衛為止,如圖(二);注意因為可沿順時針或逆時針方向改變直線的斜率,所以恰有兩條可能的線。
3. 步驟 2 所找到二線的交點,極有可能是所求的「深處」,如圖(三) 之p。

圖基的話還沒說完,護衛隊長就拿著三張圖跑了出去,將圖丟給了王國的程式設計師,並告訴他所有護衛的平面坐標,請他參考圖例寫程式計算「深處」位置。

王國的程式設計師拿到三張圖與護衛們的座標後,直接依 x 坐標將護衛們分為同等人數的兩半 (x 坐標較小的為一群,x 坐標較大的為另一群),然後再求出上述步驟 3 的交點。聰明的你應會發現,步驟 1 的均分直線選的不同的話,步驟 3 所求出的交點也可能不同,而這樣的狀況就沒有所謂的深處;然而圖基來不及提醒護衛隊長這件事,王國的程式設計師自然也不會知道了。

請寫一支程式,重現王國的程式設計師的計算結果。

Input Format

第一行有一正偶數 $n$,代表護衛人數;接下來的 $n$ 行,每行有兩個整數,分別表示一護衛在平面上的 $x$ 與 $y$ 座標,此二整數以一空白分隔。護衛的 $x$ 座標均不相同。另可確定的是,護衛人數分為兩群後,每一群護衛皆有三人不共線的特性。

Output Format

輸出 $2$ 個數字,以一空白分隔,表示王國的程式設計師計算出的「深處」之 $x$ 與 $y$ 座標;兩數字皆須四捨五入至小數點後二位。

Sample Input

輸入範例一
8
2 2
1 0
-1 2
-2 -4
0 -2
-3 -4
5 0
3 -6

輸入範例二
6
-3 4
-1 0
1 1
3 2
4 -5
-2 -3

Sample Output

輸出範例一
0.50 -1.00

輸出範例二
0.18 -0.09

Hints

評分說明
本題共有三組測試資料,每組可有多筆測試資料:
第一組測試資料,$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$

Problem Source

107北市賽
testdata set by Omelet
註:因為測資好難生所以多設了一些dependency

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 3
1 1000 524288 65536 1 2 3
2 1000 524288 65536 1 2 3
3 1000 524288 65536 1 2 3
4 1000 524288 65536 1 2 3
5 1000 524288 65536 1 2 3
6 1000 524288 65536 1 2 3
7 1000 524288 65536 1 2 3
8 1000 524288 65536 1 2 3
9 1000 524288 65536 1 2 3
10 1000 524288 65536 1 2 3
11 1000 524288 65536 1 2 3
12 1000 524288 65536 1 2 3
13 1000 524288 65536 1 2 3
14 1000 524288 65536 1 2 3
15 1000 524288 65536 1 2 3
16 1000 524288 65536 1 2 3
17 1000 524288 65536 1 2 3
18 1000 524288 65536 1 2 3
19 1000 524288 65536 1 2 3
20 1000 524288 65536 2 3
21 1000 524288 65536 2 3
22 1000 524288 65536 2 3
23 1000 524288 65536 2 3
24 1000 524288 65536 2 3
25 1000 524288 65536 2 3
26 1000 524288 65536 2 3
27 1000 524288 65536 2 3
28 1000 524288 65536 2 3
29 1000 524288 65536 2 3
30 1000 524288 65536 3
31 1000 524288 65536 3
32 1000 524288 65536 3
33 1000 524288 65536 3
34 1000 524288 65536 3
35 1000 524288 65536 3
36 1000 524288 65536 3
37 1000 524288 65536 3
38 1000 524288 65536 3
39 1000 524288 65536 3