潤羽るしあ在玩一款新遊戲,這是一款經營類的遊戲,玩家是一個航空公司的老闆,現在有許多飛機正在飛行中,因為每架飛機的航程都不同,因此只能降落在一定距離內的機場,而且因為機場腹地不夠,因此每個機場只能降落一架飛機,而玩家要分配每架飛機要降落在哪個機場(可能會有飛機無法降落,只能幫他 QQ),每成功讓一架飛機降落可以獲得 1 分,るしあ想獲得盡量多的分數,於是就向各位觀眾求救,看要怎麼分配才能使得分最高。
地圖是一個直角座標平面,每架飛機與機場都位於格子點上,計算距離時以直線距離計算。
範例:
假設飛機分別位在 $p_1=(1,2),\ p_2=(-2,2),\ p_3=(-7,-1),\ p_4=(2,3)$ ,且其航程分別為 $5,4,10,1$ 。
接著機場分別位在 $a_1=(-4,6),\ a_2=(2,-3),\ a_3=(-3,-1)$ 。
則其中一組解為 $p_2\rightarrow a_3,\ p_3\rightarrow a_1$ ,共得 $2$ 分。
而 $p_2\rightarrow a_3,\ p_3\rightarrow a_2$ 也是一組解。
第一行有兩個正整數 $N,M$ ,分別代表現在飛行中的飛機數量與機場數量。
接下來有 $N$ 行,每行有三個整數 $p_{ix},p_{iy},d_i$,第 $i$ 行代表 $i$ 號飛機目前位在 $(p_{ix},p_{iy})$ 且只能降落在距離自己 $d_i$ 以內的機場。
再接下來 $M$ 行,每行有兩個整數 $a_{ix},a_{iy}$ ,第 $i$ 行代表 $i$ 號機場位於 $(a_{ix},a_{iy})$ 。
保證所有的點(包含飛機與機場)都位於不同位置。
第一行請輸出一個整數 $s$ ,代表るしあ的得分數。
接下來 $s$ 行,每行包含兩個正整數 $l,d$ 以一個空格隔開,代表 $l$ 號飛機要降落在 $d$ 號機場, 所有的 $l$ 不得重複(不會有一架飛機同時降落在兩個機場),所有的 $d$ 不得重複(不會有兩架飛機同時降落在一個機場),輸出請以 $l$ 由小到大排序。
如果有多組解,輸出任意一組即可。
好啦我知道題敘很硬要,只是想扯到るしあ而已
るしあ最近換新造型喔,好可愛 >///<
從死靈法師進化到死靈公主了呢
PIXIV: 81438832 82483442
Youtube: Rushia Ch. 潤羽るしあ
Twitter: 潤羽るしあホロライブ3期生
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~8 | $N,M\leq10$ | 23 |
2 | 0~23 | 無特別限制 | 77 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 | |
13 | 1000 | 65536 | 65536 | |
14 | 1000 | 65536 | 65536 | |
15 | 1000 | 65536 | 65536 | |
16 | 1000 | 65536 | 65536 | |
17 | 1000 | 65536 | 65536 | |
18 | 1000 | 65536 | 65536 | |
19 | 1000 | 65536 | 65536 | |
20 | 1000 | 65536 | 65536 | |
21 | 1000 | 65536 | 65536 | |
22 | 1000 | 65536 | 65536 | |
23 | 1000 | 65536 | 65536 |