配点: 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 点):N \leq 6
- (1 点):AY_i=0, BY_i=0
- (2 点):N \leq 1000
- (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