Hostel Visit DISCUSS

#1

DISCUSS Approach for this?
with a detail explanation of question also?

I didnt understand the test case
#2

@kunalsaini8950
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

So,
Make a rocket distance function that would take x coordinate and y coordinate as parameters and return rocket distance as given in the problem statement.
When query is of type 1, find the rocket distance and push it in the max heap of size k. When max heap is full and still the query is of type 1: then:
if (pq.size() == k){
if (rocketDistance(x,y) < pq.top() )
{ //It rocket distance at top of heap is greater than current rocket dist then pop it
pq.pop();
pq.push(rocketDistance(x,y));
}
}
When query is of type 2, print the rocket distance stored at top of the heap.

Hope this helps.

#3

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.