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.

Source: codechef | Difficulty: MEDIUM
Tags: Constructive algorithms

Geometry

Complete search

Mathematics

Ad-hoc


Solutions:
import sys

class Entity:

	def __init__(self, x, y, dir):
		self.x = x
		self.y = y
		self.dir = dir

	def simulate(self, time):
		if self.dir == 'U':
			self.y += time
		elif self.dir == 'D':
			self.y -= time
		elif self.dir == 'L':
			self.x -= time
		elif self.dir == 'R':
			self.x += time

	def collision_time(self, other):
		dist_x = abs(self.x - other.x)
		dist_y = abs(self.y - other.y)
		dist = dist_x + dist_y
		self.simulate(0.5)
		other.simulate(0.5)
		cur_dist_x = abs(self.x - other.x)
		cur_dist_y = abs(self.y - other.y)
		cur_dist = cur_dist_x + cur_dist_y
		self.simulate(-0.5)
		other.simulate(-0.5)
		if cur_dist < dist and (self.x == other.x or self.y == other.y):
			return max(dist_x / 2.0, dist_y / 2.0)
		elif dist_x == dist_y and (cur_dist_x < dist_x and cur_dist_y < dist_y):
			return dist_x
		return sys.float_info.max
T = int(input())
for t in range(T):
	line = input().split()
	earth = Entity(float(line[0]), float(line[1]), line[2])
	N = int(input())
	earliest_time = sys.float_info.max
	for n in range(N):
		line = input().split()
		asteroid = Entity(float(line[0]), float(line[1]), line[2])
		earliest_time = min(earliest_time, earth.collision_time(asteroid))
	if earliest_time == sys.float_info.max:
		print('SAFE')
	else:
		print('%.1f' % earliest_time)


for i in range(int(input())):
	result = 1000
	(xe, ye, dire) = input().split()
	xe = int(xe)
	ye = int(ye)
	if dire == 'U':
		(dex, dey) = (0, 1)
	elif dire == 'D':
		(dex, dey) = (0, -1)
	elif dire == 'R':
		(dex, dey) = (1, 0)
	else:
		(dex, dey) = (-1, 0)
	n = int(input())
	for i in range(n):
		(xa, ya, dira) = input().split()
		xa = int(xa)
		ya = int(ya)
		if dira == 'U':
			(dax, day) = (0, 1)
		elif dira == 'D':
			(dax, day) = (0, -1)
		elif dira == 'R':
			(dax, day) = (1, 0)
		else:
			(dax, day) = (-1, 0)
		(vy, vx) = (day - dey, dax - dex)
		(dy, dx) = (2 * (ye - ya), 2 * (xe - xa))
		if vx == 0 and vy == 0:
			continue
		elif vx * dy == vy * dx and vy * dy >= 0 and (vx * dx >= 0):
			if vy == 0:
				val = dx / vx
			else:
				val = dy / vy
			if val < result:
				result = val
	if result == 1000:
		print('SAFE')
	else:
		print('%.1f' % (result / 2))


import sys

def read_coord():
	(x, y, d) = sys.stdin.readline().rstrip().split()
	(dx, dy) = {'U': (0.0, 1.0), 'D': (0.0, -1.0), 'L': (-1.0, 0.0), 'R': (1.0, 0.0)}[d]
	return (float(x), float(y), dx, dy)

def read_int():
	return int(sys.stdin.readline().rstrip())
testcases = read_int()
for _ in range(0, testcases):
	(xe, ye, dxe, dye) = read_coord()
	collision = None
	asteroids = read_int()
	for _ in range(0, asteroids):
		(xa, ya, dxa, dya) = read_coord()
		dxa -= dxe
		dya -= dye
		candidate = None
		if dxa != 0.0:
			t = (xe - xa) / dxa
			if ya + t * dya == ye:
				candidate = t
		elif dya != 0.0:
			t = (ye - ya) / dya
			if xa + t * dxa == xe:
				candidate = t
		if candidate is not None and candidate > 0:
			if collision is None or collision > candidate:
				collision = candidate
	if collision is None:
		print('SAFE')
	else:
		print('%.1f' % collision)


dirTable = {}
dirTable['R'] = (1, 0)
dirTable['L'] = (-1, 0)
dirTable['D'] = (0, -1)
dirTable['U'] = (0, 1)

def readCoordinates():
	(strX, strY, strDir) = input().split()
	x = int(strX)
	y = int(strY)
	(dx, dy) = dirTable[strDir]
	return (x, y, dx, dy)
t = int(input())
for test in range(t):
	(xe, ye, dxe, dye) = readCoordinates()
	n = int(input())
	shortest = 1000
	for i in range(n):
		(xa, ya, dxa, dya) = readCoordinates()
		xa -= xe
		ya -= ye
		dxa -= dxe
		dya -= dye
		if dxa == 0 and dya == 0:
			continue
		elif dxa == 0:
			if xa != 0:
				continue
			else:
				time = -ya * 1.0 / dya
				if 0 < time < shortest:
					shortest = time
		elif dya == 0:
			if ya != 0:
				continue
			else:
				time = -xa * 1.0 / dxa
				if time > 0 and time < shortest:
					shortest = time
		else:
			tx = -xa * 1.0 / dxa
			ty = -ya * 1.0 / dya
			if tx == ty and 0 < tx < shortest:
				shortest = tx
	if shortest < 1000:
		print('%.1f' % shortest)
	else:
		print('SAFE')


import sys
DIRS = dict(U=(0, 1), D=(0, -1), R=(1, 0), L=(-1, 0))
KOEF = 0.2

def div(a, b):
	return round(float(a) / b, 1)

def collide_coord(ex, edx, x, dx):
	d = abs(ex - x)
	d2 = abs(ex + edx - x)
	d3 = abs(ex - x - dx)
	if d2 > d or d3 > d:
		return False
	d_next = abs(ex + edx * KOEF - x - dx * KOEF)
	speed = abs(d_next - d)
	if speed == 0:
		if ex != x:
			return
		return 'all'
	else:
		return div(d, speed / KOEF)

def main():
	t = int(input())
	for _ in range(t):
		(ex, ey, dir) = sys.stdin.readline().strip().split()
		ex = int(ex)
		ey = int(ey)
		(edx, edy) = DIRS[dir]
		n = int(sys.stdin.readline())
		min_time = float('+inf')
		for _ in range(n):
			(x, y, dir) = sys.stdin.readline().strip().split()
			x = int(x)
			y = int(y)
			(dx, dy) = DIRS[dir]
			tx = collide_coord(ex, edx, x, dx)
			if tx is False:
				continue
			ty = collide_coord(ey, edy, y, dy)
			if ty is False:
				continue
			if tx == 'all':
				min_time = min(min_time, ty)
			elif ty == 'all':
				min_time = min(min_time, tx)
			elif tx == ty:
				min_time = min(min_time, tx)
		print(min_time if min_time < 1000000 else 'SAFE')

def __starting_point():
	main()
__starting_point()


import math

def checkpp(XE, YE, XA, YA, DIRE, DIRA, dist_to_pp):
	if DIRE == 'U':
		pXE = XE
		pYE = YE + dist_to_pp
	elif DIRE == 'D':
		pXE = XE
		pYE = YE - dist_to_pp
	elif DIRE == 'R':
		pXE = XE + dist_to_pp
		pYE = YE
	elif DIRE == 'L':
		pXE = XE - dist_to_pp
		pYE = YE
	if DIRA == 'U':
		pXA = XA
		pYA = YA + dist_to_pp
	elif DIRA == 'D':
		pXA = XA
		pYA = YA - dist_to_pp
	elif DIRA == 'R':
		pXA = XA + dist_to_pp
		pYA = YA
	elif DIRA == 'L':
		pXA = XA - dist_to_pp
		pYA = YA
	if pXE == pXA and pYE == pYA:
		return 1
	else:
		return 0
t = int(input())
for i in range(t):
	(XE, YE, DIRE) = input().split()
	(XE, YE) = (float(XE), float(YE))
	N = int(input())
	time = 300
	for n in range(N):
		(XA, YA, DIRA) = input().split()
		(XA, YA) = (float(XA), float(YA))
		if XA == XE:
			dist_to_pp = abs((YE - YA) / 2)
		elif YA == YE:
			dist_to_pp = abs((XE - XA) / 2)
		else:
			dist_to_pp = abs(XE - XA)
		if checkpp(XE, YE, XA, YA, DIRE, DIRA, dist_to_pp):
			current_time = dist_to_pp
			time = min(time, current_time)
	if time == 300:
		print('SAFE')
	else:
		print('%.1f' % time)


inp = int(input())
dirc = {'U': 'D', 'D': 'U', 'R': 'L', 'L': 'R'}
diru = {'U': [0, 1], 'D': [0, -1], 'R': [1, 0], 'L': [-1, 0]}
for i in range(inp):
	temp = input().split(' ')
	ear = [int(temp[0]), int(temp[1]), dirc[temp[2]]]
	n = int(input())
	time = []
	for j in range(n):
		temp = input().split(' ')
		temp = [int(temp[0]), int(temp[1]), temp[2]]
		coord = [ear[0] - temp[0], ear[1] - temp[1], [diru[temp[2]][0] + diru[ear[2]][0], diru[temp[2]][1] + diru[ear[2]][1]]]
		if coord[2][0] == 0 and coord[2][1] == 0:
			continue
		elif coord[2][0] == 0 and coord[2][1] != 0 and (coord[0] == 0) and (coord[1] != 0) and (coord[1] / coord[2][1] > 0):
			time += [coord[1] / coord[2][1]]
		elif coord[2][0] != 0 and coord[2][1] == 0 and (coord[0] != 0) and (coord[1] == 0) and (coord[0] / coord[2][0] > 0):
			time += [coord[0] / coord[2][0]]
		elif coord[2][0] != 0 and coord[2][1] != 0 and (coord[0] / coord[2][0] == coord[1] / coord[2][1]) and (coord[1] / coord[2][1] > 0):
			time += [coord[0] / coord[2][0]]
		else:
			continue
	if time != []:
		print(min(time))
	else:
		print('SAFE')