#P7462. [CERC2018] Shooter Island

[CERC2018] Shooter Island

题目描述

译自 [CERC2018] Shooter Island

你最近被提拔成上尉,现在你正带着你的士兵在暴风雪中执行一项特别任务。战场有点特别,因为它位于北极圈内的一个巨型冰盖上。你需要和总部协调行动。总部有很多高端的计算机协助你获得战场的最新状态。AI 接口将战场建模为一个网格。每个单元格被它所处行列号唯一确定。由单元格组成的大一些的矩形用对角线顶点的单元格对表示。最初,所有单元格被冰覆盖。

你可以从计算机端接收到两种信息:

  1. 关于打击的信息(t=0t=0):你的敌人打击了被单元格 [x1,y1][x_1,y_1][x2,y2][x_2,y_2] 描述的矩形区域,然后这个矩形区域就被冰冷的北冰洋海水淹没了;
  2. 来自你士兵的询问(t=1t=1):他们问是否可以乘船从 [x1,y1][x_1,y_1] 航行到 [x2,y2][x_2,y_2]。这条船可以用一个半径为 0.314160.31416 的圆表示。注意船体全部必须一直浮在水上,并且它不能离开战场区域。

你的士兵需要你的帮助!你能可靠地引导他们完成任务吗?

输入格式

输入第一行包含一个整数 LL,表示接下来的行数。

接下来 LL 行,每行五个整数 t,x1,y1,x2,y2t,x_1,y_1,x_2,y_2tt是信息的类型,[x1,y1][x2,y2][x_1,y_1],[x_2,y_2]表示各自的单元格。

输出格式

对于每个查询,如果可以从 [x1,y1][x_1,y_1] 乘船到达 [x2,y2][x_2,y_2],则输出 11,否则输出 00

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 如下图所示:

#1

$1≤L≤2×10^5,t ∈ {0, 1}, 1 ≤ x1, x2 ≤ 50, 1 ≤ y1, y2 ≤ 105$