Hostel Visit - Heaps

#1

Please describe the input and output
I am unable to understand

#2

@Rishab
Let us try to dry run the sample testcase for a better understanding
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

Here ,
No of queries = n = 9
k = 3

We have to print the kth distance from the hotel.

We are calculating and storing the rocket distance here i.e. (x2-x1)^2 + (y2-y1)^2 … basically the cartesian distance but without the squareroot.

First integer of each input defines the query type. 1 means take the coordinates input and 2 means display the kth distance so far.

Iteration 1 :
First we get 1 10 10
Distance = 10^2 + 10^2 = 200
We store it in our array or heap or whatever data structure we are using . Lets call it A.
A = { 200 }

Iteration 2 :
1 9 9
Distance = 9^2 + 9^2 = 162
A = { 162 , 200 }

Iteration 3 :
1 -8 -8
Distance = (-8)^2 + (-8)^2 = 168
A = { 128, 162 , 200 }

Iteration 4 :
2
A = { 128, 162 , 200 }
Time to print the 3rd nearest distance ( k=3 )
Output : 200

Iteration 5 :
1 7 7
Distance = 7^2 + 7^2 = 98
A = { 98, 128, 162 , 200 }

Iteration 6 :
2
A = { 98, 128, 162 , 200 }
Time to print the 3rd nearest distance ( k=3 )
Output : 162

Iteration 7 :
1 6 6
Distance = 6^2 + 6^2 = 72
A = { 72, 98, 128, 162 , 200 }

Iteration 8 :
1 5 5
Distance = 5^2 + 5^2 = 50
A = { 50, 72, 98, 128, 162 , 200 }

Iteration 9 :
2
A = { 50, 72, 98, 128, 162 , 200 }
Time to print the 3rd nearest distance ( k=3 )
Output : 98

Final Output :
200
162
98

Hit like if this helps you understand the question.

1 Like