Status

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

75.0% (3/4)

Description

潤羽るしあ在玩一款新遊戲，這是一款經營類的遊戲，玩家是一個航空公司的老闆，現在有許多飛機正在飛行中，因為每架飛機的航程都不同，因此只能降落在一定距離內的機場，而且因為機場腹地不夠，因此每個機場只能降落一架飛機，而玩家要分配每架飛機要降落在哪個機場(可能會有飛機無法降落，只能幫他 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$ 也是一組解。

Input Format

第一行有兩個正整數 $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})$ 。
保證所有的點(包含飛機與機場)都位於不同位置。

$N,M\leq1000$
$|p_{ix}|,|p_{iy}|,|a_{ix}|,|a_{iy}|\leq10^ 4$
$0<d_i\leq28285$

Output Format

第一行請輸出一個整數 $s$ ，代表るしあ的得分數。
接下來 $s$ 行，每行包含兩個正整數 $l,d$ 以一個空格隔開，代表 $l$ 號飛機要降落在 $d$ 號機場，所有的 $l$ 不得重複(不會有一架飛機同時降落在兩個機場)，所有的 $d$ 不得重複(不會有兩架飛機同時降落在一個機場)，輸出請以 $l$ 由小到大排序。
如果有多組解，輸出任意一組即可。

Sample Input 1

本測資即為題目敘述中的例子

4 3
1 2 5
-2 2 4
-7 -1 10
2 3 1
-4 6
2 -3
-3 -1

Sample Output 1

本測資即為題目敘述中的例子

2
2 3
3 1

Sample Input 2

3 4
0 -1 2
3 0 5
-2 2 4
-1 -3
1 0
1 3
-5 -1

Sample Output 2

3
1 2
2 1
3 3

Hints

好啦我知道題敘很硬要，只是想扯到るしあ而已
るしあ最近換新造型喔，好可愛 >///<
從死靈法師進化到死靈公主了呢

PIXIV: 81438832 82483442
Youtube: Rushia Ch. 潤羽るしあ
Twitter: 潤羽るしあホロライブ3期生

Problem Source

Subtasks

No.	Testdata Range	Constraints	Score
1	0~8	$N,M\leq10$	23
2	0~23	無特別限制	77

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (KiB)	Output Limit (KiB)	Subtasks
0	1000	65536	65536	1 2
1	1000	65536	65536	1 2
2	1000	65536	65536	1 2
3	1000	65536	65536	1 2
4	1000	65536	65536	1 2
5	1000	65536	65536	1 2
6	1000	65536	65536	1 2
7	1000	65536	65536	1 2
8	1000	65536	65536	1 2
9	1000	65536	65536	2
10	1000	65536	65536	2
11	1000	65536	65536	2
12	1000	65536	65536	2
13	1000	65536	65536	2
14	1000	65536	65536	2
15	1000	65536	65536	2
16	1000	65536	65536	2
17	1000	65536	65536	2
18	1000	65536	65536	2
19	1000	65536	65536	2
20	1000	65536	65536	2
21	1000	65536	65536	2
22	1000	65536	65536	2
23	1000	65536	65536	2

Submit