loj#P6553. 「CERC2018」Shooter Island
「CERC2018」Shooter Island
题目描述
译自 CERC 2018「G. Shooter Island」
你最近被提拔成上尉,现在你正带着你的士兵在暴风雪中执行一项特别任务。战场有点特别,因为它位于北极圈内的一个巨型冰盖上。你需要和总部协调行动。总部有很多高端的计算机协助你获得战场的最新状态。AI 接口将战场建模为一个网格。每个单元格被它所处行列号唯一确定。由单元格组成的大一些的矩形用对角线顶点的单元格对表示。最初,所有单元格被冰覆盖。
你可以从计算机端接收到两种信息:
- 关于打击的信息():你的敌人打击了被单元格 和 描述的矩形区域,然后这个矩形区域就被冰冷的北冰洋海水淹没了;
- 来自你士兵的询问():他们问是否可以乘船从 航行到 。这条船可以用一个半径为 的圆表示。注意船体全部必须一直浮在水上,并且它不能离开战场区域。
你的士兵需要你的帮助!你能可靠地引导他们完成任务吗?
输入格式
输入第一行包含一个整数 ,表示接下来的行数。
接下来 行,每行五个整数 , 是信息的类型, 表示各自的单元格。
输出格式
对于每个查询,如果可以从 乘船到达 ,则输出 ,否则输出 。
6
0 4 4 6 6
0 6 6 7 8
0 1 3 3 3
1 1 7 6 1
1 5 4 6 8
1 4 5 1 3
0
1
0
3
0 1 1 1 1
0 1 2 1 2
1 1 1 1 2
1
数据范围与提示
$1\le L\le 2\times 10^5,t\in \{0,1\},1\le x_1,x_2\le 50,1\le y_1,y_2\le 10^5$