← 返回题目列表

AtCoder · typical90_by

077. 二维平面上的平面(★7)

中文机器翻译题面 查看原题

配点: 7 点

問題文

2 在可以视为次元坐标平面的天空中,N 飞机正在航行。
i=1,2, \cdots ,N , i 第平面是时间 坐标为 0 存在于 (AX_i,AY_i) 。

所有平面都面向 您正面向 1,2,3,4,5,6,7,8 之一航行。
時刻 t 存在于 (x,y) 中存在的方向 d 航班时间 t+1 中 如果正确答案是满足

  • d=1 然后坐标 (x+1,y) 至 意思是执行将
  • d=2 然后坐标 (x+1,y+1) 至 意思是执行将
  • d=3 然后坐标 (x,y+1) 至 意思是执行将
  • d=4 然后坐标 (x-1,y+1) 至 意思是执行将
  • d=5 然后坐标 (x-1,y) 至 意思是执行将
  • d=6 然后坐标 (x-1,y-1) 至 意思是执行将
  • d=7 然后坐标 (x,y-1) 至 意思是执行将
  • d=8 然后坐标 (x+1,y-1) 至 意思是执行将

存在。
此外,飞机在飞行过程中不会改变方向。

您收到了空中交通管制员高桥先生的以下报告。 在

時刻 T 处,坐标 有一架飞机在 (BX_1,BY_1),(BX_2,BY_2), \cdots ,(BX_N,BY_N) 曾经有一架飞机在

与他的报告一致。 N 判断是否存在飞行器方向组合,如果存在,则输出示例。

制約

  • 1 \leq N \leq 20000
  • 1 \leq T \leq 10^9
  • 0 \leq AX_i,AY_i,BX_i,BY_i \leq 10^9
  • i \ne j 如果 (AX_i,AY_i) \ne (AX_j,AY_j)
  • i \ne j 如果 (BX_i,BY_i) \ne (BX_j,BY_j)
  • 输入全部为整数

小作业/分数

该问题分为多个子任务,如果您正确回答了该子任务中的所有测试用例,则视为您已正确回答了该子任务。
提交的源代码的分数是您正确回答的子作业分数的总和。

  1. (1 点):N \leq 6
  2. (1 点):AY_i=0, BY_i=0
  3. (2 点):N \leq 1000
  4. (3 点):没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

N T
AX_1 AY_1
AX_2 AY_2
 \vdots 
AX_N AY_N
BX_1 BY_1
BX_2 BY_2
 \vdots 
BX_N BY_N

出力

如果没有任何方向组合与高桥的报告不矛盾, 请输出No 。
如果存在,则采用以下格式: 请输出第 1, 2, \cdots, N 架飞机的方向,以空格分隔。然而,D_i 是一架飞机 i 方向。 在

Yes
D_1 D_2 D_3 \cdots D_N

入力例 1

3 2
3 3
5 5
9 2
11 2
5 5
3 3

出力例 1

Yes
2 6 1

時刻 T 中, 第1 平面的坐标为 (BX_2,BY_2) 存在于2 平面的坐标为 (BX_3,BY_3) 存在于3 平面的坐标为 (BX_1,BY_1) 中。


入力例 2

3 2
3 3
5 5
9 2
11 1000000000
5 5
3 3

出力例 2

No

没有任何方向的组合与高桥的报告不矛盾。


入力例 3

20 774
540130346 269080121
139837096 165633078
731188937 784167460
18996195 52176517
153153670 738204723
179733158 825294112
698198250 713974773
449248931 563096572
249863070 242694893
428066819 476630383
554127636 460973490
389988495 32320086
889782910 956212985
43905938 212030305
638141790 667879166
985957895 358743012
971007109 827787244
804625543 141347414
905270323 167192824
614855582 963943648
179733932 825294886
731188163 784166686
153154444 738205497
554128410 460973490
804626317 141348188
449249705 563096572
540129572 269079347
638142564 667878392
614855582 963944422
18996969 52177291
971007109 827788018
889782910 956213759
43906712 212031079
389987721 32319312
139836322 165633078
428067593 476631157
905271097 167192824
249862296 242694893
985958669 358742238
698199024 713975547

出力例 3

Yes
6 5 6 2 2 2 2 1 5 2 1 6 3 2 8 8 3 2 1 3