Taxis of Kharagpur are famous for making sharp turns. You are given the coordinates where a particular taxi was on a 2-D planes at N different moments: (x1, y1), (x2, y2), ..., (xN, yN). In between these coordinates, the taxi moves on a straight line. A turn at the i-th (2 ≤ i ≤ N-1) coordinate is said to be a sharp turn if the angle by which it turns at Point B = (xi, yi) when going from coordinates A = (xi-1, yi-1) to C = (xi+1, yi+1) via (xi, yi) is greater than 45 degrees. ie. suppose you extend the line segment AB further till a point D, then the angle DBC would be greater than 45 degrees.
You have to identify whether the taxi made a sharp turn somewhere or not (Please look at Output section for details). If it made a sharp turn, also identify whether it is possible to change the coordinates at one of the N moments to make sure that the taxi doesn't make any sharp turn. Note that all the N pairs of coordinates (including the new coordinates) should be integers and distinct and should have their x and y coordinates at least 0 and at most 50.

-----Input-----
- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N denoting the number of moments at which you are given the information of the taxi's coordinates.
- Each of the next N lines contains two space-separated integers xi and yi denoting the x and y coordinates of the taxi at i-th moment.

-----Output-----
- For each test case, print a single line containing two space-separated strings, either of which can be a "yes" or "no" (without quotes). If there was no sharp turn, the first string should be "yes", and if there was a sharp turn, the first string should be "no". For the second string, you should tell whether it is possible to modify at most one coordinate in such a way that taxi doesn't make a sharp turn. Note that if the first string is "yes", then the second string would always be "yes".

-----Constraints-----
- 1 ≤ T ≤ 50
- 3 ≤ N ≤ 50
- 0 ≤ xi, yi ≤ 50
- It's guaranteed that all (xi, yi) pairs are distinct.

-----Example-----
Input
5
3
0 0
1 1
2 1
3
0 0
1 0
6 1
3
0 0
1 0
1 1
4
0 0
1 0
1 1
6 1
6
0 0
1 0
1 1
2 1
2 2
3 2

Output
yes yes
yes yes
no yes
no yes
no no

-----Explanation-----
Example 1. 

You can see that taxi is never making a sharp turn.

Example 3

You can see that taxi is making a sharp turn of 90 degrees, an angle greater than 45'. However, you can change the coordinates of the third points to (2, 1) to ensure that the angle remains <= 45'.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import math
import copy
try:
	import psyco
	psyco.full()
except ImportError:
	pass

def isSharp(ang):
	return ang > math.pi / 4 + 1e-05

def unitVector(p2, p1):
	d0 = p2[0] - p1[0]
	d1 = p2[1] - p1[1]
	d = math.sqrt(d0 * d0 + d1 * d1)
	if d != 0:
		return [d0 / d, d1 / d]
	return [0, 0]

def compVectors(P):
	V = []
	for i in range(1, len(P)):
		v = unitVector(P[i], P[i - 1])
		if v[0] == 0 and v[1] == 0:
			return None
		V.append(v)
	return V

def angle(v2, v1):
	d = v2[0] * v1[0] + v2[1] * v1[1]
	if d > 1:
		d = 1
	if d < -1:
		d = -1
	return math.acos(d)

def compAngles(V):
	A = []
	for i in range(len(V) - 1):
		A.append(angle(V[i + 1], V[i]))
	return A

def updateAngles(i, P, V, A):
	if i - 1 >= 0:
		V[i - 1] = unitVector(P[i], P[i - 1])
	if i + 1 < len(P):
		V[i] = unitVector(P[i + 1], P[i])
	if i - 2 >= 0:
		A[i - 2] = angle(V[i - 1], V[i - 2])
	if i - 1 >= 0 and i + 1 < len(P):
		A[i - 1] = angle(V[i], V[i - 1])
	if i + 2 < len(P):
		A[i] = angle(V[i + 1], V[i])

def checkMoves(check, P, V, A, filled):
	for i in check:
		if i < 0 or i >= len(P):
			break
		(x, y) = P[i]
		for j in range(51):
			for k in range(51):
				P[i][0] = j
				P[i][1] = k
				if str(P[i]) in filled:
					continue
				updateAngles(i, P, V, A)
				fixed = True
				if i - 2 >= 0:
					if isSharp(A[i - 2]):
						fixed = False
				if i - 1 >= 0 and i - 1 < len(A):
					if isSharp(A[i - 1]):
						fixed = False
				if i < len(A):
					if isSharp(A[i]):
						fixed = False
				if fixed:
					return True
		P[i] = [x, y]
		updateAngles(i, P, V, A)
	return False

def canFix(first, last, P, V, A, filled):
	d = last - first
	if d > 2:
		return False
	if d == 2:
		check = [first + 2]
	if d == 1:
		check = [first + 1, first + 2]
	if d == 0:
		check = [first, first + 1, first + 2]
	if checkMoves(check, P, V, A, filled):
		return True
	return False
T = int(input())
for i in range(T):
	N = int(input())
	P = []
	V = []
	filled = {}
	for i in range(N):
		P.append(list(map(int, input().split())))
		filled[str(P[i])] = 1
	V = compVectors(P)
	A = compAngles(V)
	blunt = True
	first = -1
	last = -1
	for i in range(len(A)):
		if isSharp(A[i]):
			blunt = False
			last = i
			if first < 0:
				first = i
	if blunt:
		print('yes yes')
	elif canFix(first, last, P, V, A, filled):
		print('no yes')
	else:
		print('no no')