All Tracks Data Structures Trees Heaps/Priority Queues Problem

Hostel Visit
Tag(s):

Easy

Problem
Editorial
Analytics

Dean of NIT Silchar is going to visit Hostels of NIT Silchar. As you know that he is a very busy person so he decided to visit only first "K" nearest Hostels. Hostels are situated in 2D plane. You are given the coordinates of hostels and you have to answer the Rocket distance of Kth nearest hostel from origin ( Dean's place ) .

Input:
First line of input contains Q Total no. of queries and K
There are two types of queries:

first type : 1 x y
For query of 1st type, you came to know about the co-ordinates ( x , y ) of newly constructed hostel.
second type : 2
For query of 2nd type, you have to output the Rocket distance of Kth nearest hostel till now.

The Dean will always stay at his place ( origin ).
It is gauranted that there will be atleast k queries of type 1 before first query of type 2.

Rocket distance between two points ( x2 , y2 ) and ( x1 , y1 ) is defined as (x2 - x1)2 + (y2 - y1)2
Output:
For each query of type 2 output the Rocket distance of Kth nearest hostel from Origin.

Constraints
1 < = k < = Q < = 105
-106 < = x , y < = 106

SAMPLE INPUT
9 3
1 10 10
1 9 9
1 -8 -8
2
1 7 7
2
1 6 6 
1 5 5
2
SAMPLE OUTPUT
200
162
98
Explanation

The rocket distance of first k ( = 3 ) hostels in increasing order are 128 , 162 , 200
The Rocket distance of 3rd nearest hostel till now is 200.
After another query of type 1 , the rocket distance of hostels in increasing order are 98 ,128 , 162 , 200.
The Rocket distance of 3rd nearest hostel till now is 162.
After 2 query of type 1, the rocket distance of hostels in increasing order are 50 , 72 ,98 , 128 ,162 , 200.
The Rocket distance of 3rd nearest hostel till now is 98.

Problem Setter : Satyam Swarnkar

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

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications