Server Time:

User's AC Ratio in this contest

0.0% (0/4)

Submission's AC Ratio in this contest

0.0% (0/21)

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