[Solution] Three Points solution codechef

Three Points solution codechef


There are three distinct points – A,B,CA,B,C in the XYX−Y plane. Initially, you are located at point AA. You want to reach the point CC satisfying the following conditions:

  • You have to go through point B.
  • You can move in any of the four axis-parallel directions (+X+XX−X+Y+YY−Y direction). However, you can make at most one turn in the path from AA to CC.

Determine if it is possible to reach the destination CC satisfying the above conditions.

NOTE:

  • One turn means 9090∘ clockwise or anticlockwise rotation along the direction of movement. For example, if you are moving towards the +X+X direction, after one turn you can move either in the +Y+Y direction or in the Y−Y direction. Changing the direction by 180180∘ is not allowed.

Input Format Three Points solution codechef

  • The first line of input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains two space-separated integers XA,YAXA,YA, denoting the coordinates of the starting point A.
  • The second line of each test case contains two space-separated integers XB,YBXB,YB, denoting the coordinates of the point B.
  • The third line of each test case contains two space-separated integers XC,YCXC,YC, denoting the coordinates of the finishing point C.

Output Format Three Points solution codechef

For each test case, print a single line containing one string – "YES"(without quotes) if it is possible to reach the finishing point satisfying the above conditions, otherwise print "NO"(without quotes).

Constraints Three Points solution codechef

  • 1T21051≤T≤2⋅105
  • 109XA,YA,XB,YB,XC,YC109−109≤XA,YA,XB,YB,XC,YC≤109
  • The three points are pairwise distinct

Sample Input 1 

4
1 1
1 3
3 3
0 0
2 2
3 4
5 2
3 2
1 2
1 1
-1 1
10000 10000

Sample Output 1 

YES
NO
YES
NO

Explanation

  • Test case 11: You start moving in the +Y+Y direction from A=(1,1)A=(1,1), after two-unit steps you reach the point B=(1,3)B=(1,3). Then you make a clockwise turn at point BB and start moving towards the +X+X direction. After two-unit steps, you reach the finishing point C=(3,3)C=(3,3).

  • Test case 22: There is no possible way to reach the finishing point CC satisfying the above conditions. You have to make at least two turns in the path.

  • Test case 33: You start moving in the X−X direction from A=(5,2)A=(5,2) . After 4 unit steps, you reach the finish point C=(1,2)C=(1,2). In the path from AA to CC, you go through the point B=(3,2)B=(3,2) and don’t make any turn.

Solution: Click here

 

Leave a Comment