All Tracks Math Problem

Rocket
Tag(s):

Basic Geometry, Circles, Datastructures, Hard, Math

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, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

July Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?