Collision in Space

Problem code: COLLIDE

All submissions for this problem are available.

Did you hear about the Nibiru collision ? It is a supposed disastrous encounter between the earth and a large planetary object. Astronomers reject this idea. But why listen to other people's beliefs and opinions. We are coders above all, so what better way than to verify it by a small code. The earth and N asteroids are in the 2D plane. Each of them is initially located at some integer coordinates at time = 0 and is moving parallel to one of the X or Y axis with constant velocity of 1 unit per second.

Direction of movement is given as 'U' ( Up = towards positive Y ), 'D' ( Down = towards negative Y ), 'R' ( Right = towards positive X ), 'L' ( Left = towards negative X ). Given the initial position and the direction of movement of the earth and each of the N asteroids, find the earliest time at which the earth collides with one of the asteroids. If there can not be any collisions with the earth, print "SAFE" ( without quotes ). You can ignore the collisions between asteroids ( i.e., they continue to move in same direction even after collisions between them ).

Input

First line contains T, number of test cases. T cases follow. In each test case, first line contains XE YE DIRE, where (XE,YE) is the initial position of the Earth, DIRE is the direction in which it moves. Second line contains N, the number of asteroids. N lines follow, each containing XA YA DIRA, the initial position and the direction of movement of each asteroid. No asteroid is initially located at (XE,YE)

Output

For each test case, output the earliest time at which the earth can collide with an asteroid (rounded to 1 position after decimal). If there can not be any collisions with the earth, print "SAFE" (without quotes).

Constraints

1 ? T ? 10
1 ? N ? 2012
-100 ? XE, YE, XA, YA ? 100
(XE,YE) != any of (XA,YA)
DIRE, DIRA is one of 'U', 'R', 'D', 'L'

Example

Input:
3
0 0 R
2
1 -2 U
2 2 D
1 1 U
1
1 0 U
0 0 R
1
3 0 L

Output:
2.0
SAFE
1.5

Explanation:

Case 1 :
Time 0 - Earth (0,0) Asteroids { (1,-2), (2,2) }
Time 1 - Earth (1,0) Asteroids { (1,-1), (2,1) }
Time 2 - Earth (2,0) Asteroids { (1,0 ), (2,0) }

Case 2 :
The only asteroid is just one unit away below the earth and following us always, but it will never collide :)

Case 3 :
Time 0 - Earth (0,0) Asteroid (3,0)
Time 1 - Earth (1,0) Asteroid (2,0)
Time 1.5 - Earth (1.5,0) Asteroid (1.5,0)


Note : There are multiple test sets, and the judge shows the sum of the time taken over all test sets of your submission, if Accepted.

Author: flying_ant
Date Added: 9-01-2012
Time Limit: 2 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

if the input fails some

mangatmodi @ 22 Jan 2012 10:16 PM
if the input fails some constraints, then how to report error? or should we assume that the input will always be valid?

yes, you can safely assume

anil_adm @ 22 Jan 2012 10:18 PM
yes, you can safely assume that the input will always be valid !

Could you please give a few

randomks @ 22 Jan 2012 10:24 PM
Could you please give a few more test cases ? My code works well on my machine but its giving wrong answer here

@randomks : The contest it

anil_adm @ 22 Jan 2012 10:29 PM
@randomks : The contest it still live, so we can't provide any more hints / sample cases. We do not entertain such questions now.

Answer should print upto one

khndlwlpnkj @ 22 Jan 2012 10:34 PM
Answer should print upto one digit after decimal or can be more ?

@khndlwlpnkj : print

anil_adm @ 22 Jan 2012 10:40 PM
@khndlwlpnkj : print *exactly* one digit after decimal

The sample input given does

pseudopenggy @ 22 Jan 2012 10:54 PM
The sample input given does not follow the input format.

Are xa,ya,xe,ye integers or

phantom11 @ 22 Jan 2012 10:56 PM
Are xa,ya,xe,ye integers or decimals??

@pseudopenggy : We verified

anil_adm @ 22 Jan 2012 10:56 PM
@pseudopenggy : We verified it again and it follows. If you found any specific fault, please let us know where the exact mistake is.

@phantom11: All are integers

harsha_adm @ 22 Jan 2012 10:59 PM
@phantom11: All are integers

can xa,ya or xe,ye be a

ediston @ 22 Jan 2012 11:00 PM
can xa,ya or xe,ye be a decimal ?? or only integers

at case 1: N = 2 but there

pseudopenggy @ 22 Jan 2012 11:01 PM
at case 1: N = 2 but there are 3 given asteroids case 2: N = 1 but there are 2 given asteriods *Second line contains N, the number of asteroids. N lines follow, each containing XA YA DIRA, the initial position and the direction of movement of each asteroid.

@ediston: Only integers

anil_adm @ 22 Jan 2012 11:02 PM
@ediston: Only integers

@pseudopenggy : Read the

anil_adm @ 22 Jan 2012 11:03 PM
@pseudopenggy : Read the input section again carefully. If N = 2, then the next 2 lines contain information of the 2 asteroids. The 3rd line is actually the beginning of next test case, note that each test case starts with the coordinates of the earth and its direction in the first line.

Missed that out. Thanks.

pseudopenggy @ 22 Jan 2012 11:05 PM
Missed that out. Thanks.

In the last line of first

critical @ 22 Jan 2012 11:08 PM
In the last line of first paragraph, it is written that initially each " is moving parallel to one of the X or Y axis". But in the sample input the asteroids move UP or DOWN. Does it mean the asteroids changed their course later on???

@critical : Each Asteroid is

anil_adm @ 22 Jan 2012 11:12 PM
@critical : Each Asteroid is located initially at some integer coordinates and moves in one of the 4 specified directions. They do not change their course ever. You can ignore the collisions between asteroids.

my time is 0.05 and memory is

ediston @ 22 Jan 2012 11:17 PM
my time is 0.05 and memory is 2.6 M still it is not accepted. But some guys has 0.13 and 2.6M .. still it is accepted. please explain soon... :)

@ediston : The correctness of

anil_adm @ 22 Jan 2012 11:21 PM
@ediston : The correctness of your solution doesn't depend on the memory or time taken. As long as it runs under the time limit using memory with in the limits, it is ok. Your algorithm and taking care of corner cases, is more important.

if my program is printing 2

lallu1 @ 22 Jan 2012 11:21 PM
if my program is printing 2 instead of 2.0, it is valid????

"Runtime Error" doesn't mean

ediston @ 22 Jan 2012 11:25 PM
"Runtime Error" doesn't mean all test cases passing but more memory taken ?

@lallu1 : No, its not valid.

anil_adm @ 22 Jan 2012 11:28 PM
@lallu1 : No, its not valid. Exactly one digit should be printed after decimal. @ediston: RuntimeError can be due to many reasons. Please refer FAQ section.

Is "iomanip" library file

mangatmodi @ 22 Jan 2012 11:46 PM
Is "iomanip" library file available in C++?

@mangatmodi : sorry,we do not

anil_adm @ 22 Jan 2012 11:49 PM
@mangatmodi : sorry,we do not answer such queries during a live match. Please refer the FAQ section for more details.

i am able to solve each test

vamsi_algo @ 22 Jan 2012 11:51 PM
i am able to solve each test case with O(no : asteroids) it is giving TIME LIMIT EXCEEDED. is there any better approach than this ? jst tell me yes or no

No. May be some

anil_adm @ 22 Jan 2012 11:55 PM
No. May be some implementation mistake.. please go through your code thoroughly.

tough one :P

vfix @ 22 Jan 2012 11:57 PM
tough one :P

Please post some sample test

rahul_code @ 23 Jan 2012 12:06 AM
Please post some sample test case..My code is working fine on all test case but showing wrong answer. PS. contest is over so you can post sample test cases.

When will this problem be

softarn @ 23 Jan 2012 12:12 AM
When will this problem be available to test again?

please give more test case

sisa @ 23 Jan 2012 12:35 AM
please give more test case

@softarn: The problems has

admin @ 23 Jan 2012 07:35 AM

@softarn: The problems has been moved into the practice section. You can submit your solutions there.

@cool123.. My code is almost

ediston @ 23 Jan 2012 05:21 PM
@cool123.. My code is almost exactly the same.. Even I am not sure what is wrong here..

i didn't participate in the

codechampion @ 23 Jan 2012 06:00 PM
i didn't participate in the competition. is there a way now to submit my code and check whether it is correct?

@ediston: Both of us did a

cool123 @ 23 Jan 2012 08:19 PM
@ediston: Both of us did a silly mistake. We dint check for coordinates when they r opposite. Eg: When the earth is U and asteroid is D we dint check whether earth is below the asteroid :) I corrected and submitted :) http://www.codechef.com/viewsolution/807147.

can't i submit my code now

turjachaudhuri @ 14 Feb 2012 04:24 PM
can't i submit my code now and check whether it is correct or not...........????i hope there is such an option.........please let me now :)

under which category is this

turjachaudhuri @ 14 Feb 2012 06:32 PM
under which category is this problem????

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions