All Tracks>Algorithms> Searching> Binary Search> Problem
Minimum radius
★★★★★

3.7

6 votes
Binary Search, Algorithms, C++
Problem

You are given two arrays X and Y of N elements denoting N points on the 2D plane. You are given another array A of N elements denoting the values associated with each point.

You have to find the minimum integer value radius r of a circle with the center (0,0) such that the sum of all the values of nodes within the circle or on the circle is greater than or equal to an integer p.

If any such r does not exist, print -1.

Notes

  • Assume 1-based indexing.
  • For a circle with radius 0, the center is said to lie inside that circle.

Input

  • The first line contains an integer T denoting the number of test cases.
  • For each test case:
    • The first line contains two space-separated integers N, p.
    • The second line contains N space-separated integers denoting the array X.
    • The third line contains N space-separated integers denoting the array Y.
    • The fourth line contains N space-separated integers denoting the array A.

Output

For each test case in a new line, print the minimum integer value radius r of the required circle.

Constraints

1≤T≤101≤N≤1050≤p≤109−108≤X[i],Y[i]≤1080≤A[i]≤104

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
  • If radius r is choosen to be 2. Following points are inside the circle.
    • Point (1,0) with value 1
    • Point (2,0) with value 2
    • Sum of values of points is 3.
  • Thus, required answer is 2
Editor Image

?