Hostel visit doubt

#1

I’m unable to understand this problem properly.

#2

Hey @anika203a
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 = { 200,162 }since max heap

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

Iteration 4 :
2
A = { 200 ,162,128}
Time to print the 3rd nearest distance which is at root
Output : 200

Iteration 5 :
1 7 7
Distance = 7^2 + 7^2 = 98
since smaller than root , remove root and push it because we will always mantain k elements
A = { 162,128,98}

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

Iteration 7 :
1 6 6
Distance = 6^2 + 6^2 = 72
since smaller than root , remove root and push it because we will always mantain k elements
A = { 128,98,72}

Iteration 8 :
1 5 5
Distance = 5^2 + 5^2 = 50
since smaller than root , remove root and push it because we will always mantain k elements
A = { 98,72,50}

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

Final Output :
200
162
98

1 Like
#3

Okay thanks for explaining !!

1 Like
#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.