Czech Technical University in Prague
ICPC Foundation
Czech ACM Chapter
Central Europe Regional Contest 2018
Shooter Island
island.c, island.cpp, Island.java, island.py
You were recently promoted to captain and your troopers are now operating on a special mission
in a storm. The battlefield is kind of extraordinary, it is located above the Arctic Circle on a huge
ice floe. You coordinate the actions from the headquarters. There are many high-end computers
keeping you up to date on the developments at the battlefield, which is modeled by the AI
interface as a grid of unit squares. Each unit square is identified by its row and column index
in the grid. Bigger rectangles, consisting of unit squares, are described by a pair of unit squares
in the opposite corners of the rectangle. At the beginning, all squares are covered with ice.
There are two important types of information you receive from the computers:
0. Information about hits: Your enemy hit a rectangle described by unit squares [x1,y1] and
[x2,y2]. This rectangle is then immediately flooded by cold arctic water.
1. A query by your troopers: They ask whether it is possible to go from square [x1,y1] to
[x2,y2] by a boat. The boat may be represented by a circle of radius 0.31416. Note that
the boat has to stay fully on water surface all the time and it is not allowed to leave the
battlefield area.
Your troopers need your help! Can you guide them reliably?
Input Specification
The first input line contains an integer L (1 ≤ L ≤ 2 · 105 ), the number of lines to follow.
Each of the next L lines contains five integers t, x1, y1, x2, y2 (t ∈ {0, 1}, 1 ≤ x1, x2 ≤ 50,
1 ≤ y1, y2 ≤ 105 ). Number t is the type of information and pairs [x1, y1] and [x2, y2] specify the
respective unit squares.
Output Specification
For each query, output 1 if it is possible to sail from unit square [x1,y1] to unit square [x2,y2],
and 0 otherwise.
Output for Sample Input 1
Sample Input 1
0
6
1
0
4
4
6
6
0
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
Sample Input 2
Output for Sample Input 2
3
1
01111
01212
11112
Figure 1: Illustration of Sample Input 1.
