Minimizing Direction Changes for a Humanoid Cleaning Robot

Prof. Pang has purchased a humanoid cleaning robot to clean his yard. The robot can only move in a straight line or change its direction (i.e. make a turn). The yard is modeled as a 2D plane. The robot is currently at point \(A\) and needs to move to point \(B\) to perform cleaning. However, there are two straight walls given by segments \(CD\) and \(EF\) in the yard. The robot will fall over if it touches any part of these walls (including their endpoints).

Since Prof. Pang is lazy, he wants to minimize the number of times the robot changes direction. In other words, you need to plan a piecewise linear path from \(A\) to \(B\) with as few turns as possible such that none of the line segments of the path intersect (or even touch) any of the two walls. It can be proven that a solution using at most two turns always exists. Your task is to output the minimum number of turns needed.

Note: A turn is counted every time the robot changes its moving direction. If the robot goes directly from \(A\) to \(B\) without any turn then the answer is 0.

The answer should be 0 if a direct path from \(A\) to \(B\) is safe (i.e. does not intersect either wall), 1 if a safe path with one turn exists, and 2 otherwise.

All formulas are in \( \LaTeX \) format.

inputFormat

The input consists of six lines. Each line contains two space‐separated numbers representing the coordinates of a point. The points are given in the following order:

1. Coordinates of \(A\) (starting point).
2. Coordinates of \(B\) (destination).
3. Coordinates of \(C\) (first endpoint of the first wall).
4. Coordinates of \(D\) (second endpoint of the first wall).
5. Coordinates of \(E\) (first endpoint of the second wall).
6. Coordinates of \(F\) (second endpoint of the second wall).

All coordinates are real numbers. You can assume that the walls do not degenerate into points.

outputFormat

Output a single integer representing the minimum number of times the robot needs to change its direction (i.e. the minimum number of turns), which will be 0, 1, or 2.

sample

0 0
10 0
0 1
10 1
5 -5
5 -6

0