TINKUJOB - Tinku got a job

no tags 

Tinku has a new job at BIT. The job pays well, and provides Tinku with a house to live within BIT. His only job is to deliver goods to Main Building. The goods are to be collected from a pickup point. Therefore, a typical day of work for Tinku begin with him leaving his home, collecting the goods from the pickup point, and ends with him delivering the goods to the Main Building. Pickup points are arbitrary locations in the BIT campus.

The whole BIT campus can be represented as a 2-D plane. Tinku's House, Main Building and pickup points can only be present at integer coordinates. You are given the coordinates of Tinku's house and the Main Building (See the input format carefully). The distance considered is the euclidean distance, i.e, distance from point (a, b) to (c, d) will be sqrt((a-c)^2 + (b-d)^2). A main building can also be a pickup point.

The job contract ensures that Tinku works atmost for H hours. Tinku is new at this job, and is very nervous. ACM people being friendly as always, decide to ease him up by finding the number of possible pickup points such that Tinku is able to finish his work.

 

Input

First line denotes number of test cases T
T test cases follow
Each test case is formatted as:
First line consist of integers A, B, C, H, V
Tinku's house is at coordinate (A, C), and Main Building is at (B, C)
Tinku works at most for H hours and has walks with a speed of V units/hour

T = 1000
-100 <= A, B, C <= 100
0 < V <= 40
0 < H <= 40

Output

A single line with the number of possible pickup points

Example

Input:
2
1 -1 0 1 3
-5 5 10 2 2
Output: 5
0

hide comments
(Tjandra Satria Gunawan)(曾毅昆): 2015-02-25 22:44:04

Be careful of precision error.
Definitely hard problem! Just like AVMG2 ;-)

:D: 2015-02-20 19:18:54

Well, the problem gets my seal of approval. Thanks for setting it up.

darol: 2015-02-17 22:02:17

How big is campus? (-100,-100)x(100,100) plane or infinite plane - for example for 0 0 0 40 40 answer is 40401 (limited campus) or more(infinite)?
whats time limit for java?

re(vamsi): I am not sure about the plane(likely infinite), timelimit is same for all languages, which is in this case 0.5s per a testfile.

Last edit: 2015-02-26 04:44:45
Vamsi Krishna Avula: 2015-01-29 16:24:26

@nims11, my code may not be optimal but is this problem solvable in Python?
and also are h and v integers?

Re: yes, h and v are integers, and I believe the problem is solvable in python. I will try to code it in python and if any issues, will update the time limit.

Last edit: 2015-01-29 16:02:51
ivar.raknahs: 2015-01-29 16:24:26

can Tinku's House and Main Building be considered as a pick up point?

re(nims11): yes

Last edit: 2015-01-29 17:34:29

Added by:VV
Date:2015-01-28
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Own problem (CQM 4, BIT Mesra)