Rocket
Tag(s):

## Basic Geometry, Circle, Datastructures, Hard, Mathematics

Problem
Editorial
Analytics

Country A and B are in war. Assumption, the battle field is in 2D coordinate. Country B have built a defend system containing "rocket defense system" (RDS) and "wall". A RDS has radius $R$, that means if a rocket is at distance less than or equals $R$ from the RDS then it is detected and destroyed. A wall can be considered as a straight segment, a rocket will be resisted if hitting it (both ends inclusive). At position $(0, 0)$, country A shoots rockets along a straight line to a target. You are given $Q$ queries of several types:

$1\ x\ y$: Country A shoot a rocket to position $(tx, ty)$, you must answer whether it sucessfully reaches the target or find position where it is destroyed by a RDS or hits a wall.

$2\ x\ y$: Country B builds a RDS at position $(x, y)$.

$3\ x\ y\ z\ t$: Country B builds a wall between two positions $(x, y)$ and $(z, t)$.

$4\ u$: $u$-th RDS is destroyed by an army of country A.

$5\ v$: $v$-th wall is destroyed by an army of country A.

Input Format

The first line contains four space-separated integers $N, M, R, Q$ denoting the number of RDSs, the number of walls, the radius of RDS and the number of queries, respectively.

Each of the $N$ next lines contains two space-separated integers $x, y$ denoting position of a RDS.

Each of the $M$ next lines contains four space-separated intergers $x, y, z, t$ denoting position of a wall.

$Q$ lines follow, each line contains a query as described above.

RDSs and walls are numbered according to their appearance.

Output Format

For each query of the first type, assuming $d$ is euclidean distance the rocket goes before stopping (it is destroyed or resisted or reaches the target). Print the nearest integer to $1000 \times d$ ($.5$ is rounded up).

Constraints

• $1 \le N, M \le 5\times10^4$
• $1 \le R \le 10^6$
• $1 \le Q \le 10^5$
• $1 \le x, y, z, t, tx, ty \le 10^6$
• No RDS covers point $(0, 0)$
• $1 \le u \le$ the number of RDSs at that time (destroyed include)
• $1 \le v \le$ the number of walls at that time (destroyed include)
• Total numbers of RDSs and walls is at most $5\times 10^4$

SAMPLE INPUT
1 1 1 3
5 1
2 3 8 3
1 3 3
1 5 1
1 8 3

SAMPLE OUTPUT
4243
4099
4459
Explanation

Query 1: Distance = $3\sqrt{2} \approx 4.242640687$, so we print $4243$.

Query 2: Distance $= \sqrt{26} - 1 \approx 4.099019514$, so we print $4099$.

Query 3: Distance $\approx 4.459387150$, so we print $4459$.

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

July Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Counting
• Algorithms > Graphs
• Math > Number Theory
• Algorithms > Searching
• Algorithms > Searching