Cross the river
Tag(s):

Algorithms, Breadth-first search, Dijkstra's algorithm, Graph, Graph Theory, Graphs, Hard, Shortest Path Algorithms, Shortest path problem, approved

Problem
Editorial
Analytics

You are required to cross a river to reach your destination. The streamflow of the river was fast, therefore, you cannot cross the river by swimming.

The river is available at the X-axis and its boundary is marked by Y coordinates, from $y = A$ to $y = B$.

--------------------------------------------------------------------------------- $(y=A)$

..................................................................................................

..................................................................................................

..................................................................................................

---------------------------------------------------------------------------------- $(y=B)$

You are provided with some rocks along with their centers and radius respectively. Currently, you are standing on the shore $y = B$. You cannot jump between rocks but can move from one rock to another if both rocks overlap at some point. You are required to determine whether you will be able to cross the river by using rocks or not. If you can cross the river, then print the minimum number of rocks that are required to cross the river. Otherwise, print $-1$.

Input format

• First line: $T$ denoting the number of test cases
• For each of the test case:
• First line: $N$ denoting the number of rocks
• Second line: $N$ lines containing three integers $X, Y, R$ where $(X,Y)$ denotes the coordinates of the center of that rocks and $R$ denotes its radius
• Third line: Two integers $A$ and $B$ denoting the upper and lower boundary of the river respectively

Output format

Print the required answer in a separate line for each of the test case.

Constraints

$1 \le T \le 10$
$1 \le N \le 5000$
$-10^9 \le X, Y, A, B \le 10^9$
$1 \le R \le 10^9$
$B < A$

SAMPLE INPUT
1
3
1 1 2
1 2 1
3 4 1
3 0

SAMPLE OUTPUT
1

Explanation

At first we can step onto the first rock from the river shore. Then we can cross river directly or can move to second rock and then cross it. Note that we can't use third rock as it is beyond the reach from the other rocks.

Time Limit: 2.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: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...

Contributor

Challenge Name

Java Easy : Mock Online Coding Assessments

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming
• Algorithms > Searching
• Algorithms > Searching
• Math > Combinatorics
• Algorithms > Dynamic Programming
• Algorithms > Sorting
• Algorithms > String Algorithms
• Algorithms > Searching
• Algorithms > String Algorithms
• Algorithms > Dynamic Programming
• Algorithms > Graphs
• Algorithms > Dynamic Programming
• Algorithms > Greedy Algorithms
• Math > Combinatorics
• Basic Programming > Implementation
• Algorithms > Dynamic Programming

?