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