681 . 兵營調度問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

40.0% (2/5)

Tags

apcsc apcsc-ds

Description

在一個座標平面上，原點有一座敵人的城堡，而我軍要在其他座標上部屬許多部隊。
精確來說，每個部隊是由一排排好的士兵組成，且我們稱一個部隊內排最前面的為前排士兵，排最後面的為後排士兵。
由於最近這個地區動盪不安，敵軍城堡頻有動作，因此需要不斷調度兵力以抵禦敵人。

總結來說依序共有 N 個兵力調度事件，分成四類：

  1. 座標 (x,y) 的部隊空降一名編號為 i 的士兵成為前排士兵。
  2. 座標 (x,y) 的部隊空降一名編號為 i 的士兵成為後排士兵。
  3. 座標 (x,y) 的部隊請求一名前排士兵，到該部隊前排支援。
  4. 座標 (x,y) 的部隊請求一名後排士兵，到該部隊後排支援。

事件3、4中，前排士兵要由其他部隊的前排士兵來支援，後排士兵要由其他部隊的後排士兵來支援。且支援會由安全度最接近的部隊來派兵（安全度定義為與敵人城堡距離的平方。若安全度之差相同，則選擇 x 較小的部隊。若 x 仍相同，則選擇 y 較小的部隊。）。

最初，我軍在地圖上沒有任何士兵。求 N 個事件後，每個編號的士兵待在哪個座標。

Input Format

輸入第一行有一個正整數 N，代表有多少事件。
接下來 N 行每行都會是下列其中一種

  1. 1 x y i 座標 (x,y) 的部隊空降一名編號為 i 的士兵成為前排士兵
  2. 2 x y i 座標 (x,y) 的部隊空降一名編號為 i 的士兵成為後排士兵
  3. 3 x y 座標 (x,y) 的部隊請求一名前排士兵
  4. 4 x y 座標 (x,y) 的部隊請求一名後排士兵
  • 1≤N≤3⋅105
  • −109≤x,y≤109
  • 若 xa2+ya2=xb2+yb2 則 (xa,ya)=(xb,yb)
  • i 兩兩不重複
  • 1≤i≤N
  • 在事件 3, 4中，保證請求得到支援。

Output Format

令 M 為士兵的數量。
請輸出 M 行，第 j 行請輸出編號第 j 小的士兵所在的座標，以一個空白隔開。

Sample Input 1

3
1 125083899 290965564 3
1 125083899 290965564 2
1 125083899 290965564 1

Sample Output 1

125083899 290965564
125083899 290965564
125083899 290965564

Sample Input 2

12
2 873458049 428337058 9
2 873458049 428337058 11
4 -481510690 29429158
2 -481510690 29429158 12
3 -861066800 -998324814
2 873458049 428337058 2
2 873458049 428337058 7
4 -861066800 -998324814
1 873458049 428337058 10
1 873458049 428337058 3
4 -861066800 -998324814
1 -861066800 -998324814 1

Sample Output 2

-861066800 -998324814
-861066800 -998324814
873458049 428337058
-861066800 -998324814
-861066800 -998324814
873458049 428337058
-481510690 29429158
-481510690 29429158

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~54 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
24 1000 524288 65536 2
25 1000 524288 65536 2
26 1000 524288 65536 2
27 1000 524288 65536 2
28 1000 524288 65536 2
29 1000 524288 65536 2
30 1000 524288 65536 2
31 1000 524288 65536 2
32 1000 524288 65536 2
33 1000 524288 65536 2
34 1000 524288 65536 2
35 1000 524288 65536 2
36 1000 524288 65536 2
37 1000 524288 65536 2
38 1000 524288 65536 2
39 1000 524288 65536 2
40 1000 524288 65536 2
41 1000 524288 65536 2
42 1000 524288 65536 2
43 1000 524288 65536 2
44 1000 524288 65536 2
45 1000 524288 65536 2
46 1000 524288 65536 2
47 1000 524288 65536 2
48 1000 524288 65536 2
49 1000 524288 65536 2
50 1000 524288 65536 2
51 1000 524288 65536 2
52 1000 524288 65536 2
53 1000 524288 65536 2
54 1000 524288 65536 2
Submit
Back to Top