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'.

Difficulty: interview

Starter code:

Solutions:
import math
import copy
try:
 import psyco
 psyco.full()
except ImportError:
 pass
 
def isSharp(ang):
 return ang > math.pi/4 + 0.00001
 
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')
 else:
  if canFix(first, last, P, V, A, filled):
   print('no yes')
  else:
   print('no no') 

import math
import copy
try:
 import psyco
 psyco.full()
except ImportError:
 pass
 
def isSharp(ang):
 return ang > math.pi/4 + 0.00001
 
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')
 else:
  if canFix(first, last, P, V, A, filled):
   print('no yes')
  else:
   print('no no')