1. Problem

  BOJ_17386 and BOJ_17387 are the intersection of two lines problems solved by Counter Clockwise(CCW) algorithm. The levels of problem are Gold 3 and Gold 2, respectively.(Link of BOJ 17386)
(Link of BOJ 17387)

Inputs

  • There are two line $L_1$ and $L_2$ in $\mathbb{Z}^2$.
  • The endpoints of $L_1$ is $(x_1, y_1)$ and $(x_2, y_2)$.
  • The endpoints of $L_2$ is $(x_3, y_3)$ and $(x_2, y_2)$.
  • ${-1,000,000 \leq x_1, x_2, x_3, x_4, y_1, y_2, y_3, y_4 \leq 1,000,000} \in \mathbb{Z}$
  • The length of $L_1$ and $L_2$ is greater than 0.
  • Only BOJ 17387 If an endpoint of a line is on the another line or equal an endpoint of the another line, the two lines intersect.

Outputs

  • If the two lines intersect, then output 1, else 0.

Time & Space Limit

  • Time limit: 0.25 sec
  • Space limit: 512 MB



2. Approach to the problem

  We can solve the problem using CCW algorithm. Since the endpoints of lines is integer,the endpoints will be same or far from each other. So, we don’t need to consider the error in the floating point arithmetic. I will solve BOJ 17387, because this problem is the same as adding some conditions to BOJ 17386.



3. CCW algorithm

  CCW is the concept of geometry. Given $p_1$, $p_2$ and $p_1$, compute whether $p_3$ is clockwise or counterclockwise relative to the direction from $p_1$ to $p_2$. We can compute this problem using cross product of $\overrightarrow{p_1 p_2}$ and $\overrightarrow{p_1 p_3}$. Note that there are the property of cross product of $v_1$ and $v_2$.

Fig 1. Cross product

  • $p_1 = (x_1, y_1, 0), p_2 = (x_2, y_2, 0), p_3 = (x_3, y_3, 0)$
  • $v_1 = \overrightarrow{p_1 p_2} = (x_2 - x_1, y_2 - y_1, 0)$
  • $v_2 = \overrightarrow{p_1 p_3} = (x_3 - x_1, y_3 - y_1, 0)$
  • The result vector $v_3$ of cross product of $v_1$ and $v_2$ is orthogonal.
  • So, x-coordinate and y-coordinate of $v_3$ will be 0. And the direction of $v_3$ is depended on z-coordinate.
  • By the right hand rule, if the direction of $v_3$ is positive, $p_3$ is counterclockwise relative to the direction of $v_1$. And if the direction is 0, then $p_3$ is collinear. Else(the direction is negative), $p_3$ is clockwise relative.

Fig 2. CCW and the z-coordinate of the result of cross product

  So, we can compute the direction relation of $p_1$, $p_2$ and $p_3$, using cross product. We can simply cross product formula like below, since we only need the sign of $v_3$. Finally, we compute CCW in $O(1)$ time.

  • Cross Product of $\vec{a} = <a_1, a_2, a_3>, \vec{b} = <b_1, b_2, b_3>$ \(\vec{a} \times \vec{b} = \begin{vmatrix} i & j & k\\ a_1 & a_2 & a_3\\ b_1 & b_2 & b_3\end{vmatrix} = (a_2 b_3 - a_3 b_2)i - (a_1 b_3 - a_3 b_1)j + (a_1 b_2 - a_2 b_1)k\)

  • Applied to CCW \(\overrightarrow{p_1 p_2} \times \overrightarrow{p_1 p_3} =\begin{vmatrix} i & j & k\\ (x_2 - x_1) & (y_2 - y_1) & 0\\ (x_3 - x_1) & (y_3 - y_1) & 0 \end{vmatrix}\) \(= \text{we need only z-coordinate, } (x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1)\)

Practice) BOJ_11758 is the CCW problems. The levels of problem are Gold 5.(Link of BOJ 11758)



4. Apply CCW algorithm to the problem

Fig 3. Computing intersection of two line using CCW

  We can solve the intersection of two lines problem, using CCW algorithm 4 times. If the relation of the endpoints of $L_2$ with $L_1$ is different, then the endpoints of $L_2$ is on different sides based on $L_1$. However, we have to check reverse. You can understand it if you look at the figure above.

Fig 4. Two cases when CCW is 0

  In BOJ 17387, we have one more condition of intersection, “If an endpoint of a line is on the another line or equal an endpoint of the another line, the two lines intersect.” It means we need to check more thing when the result of CCW algorithm is 0. In that case, $L_1$ and $L_2$ overlap or $L_1$ and $L_2$ is not overlap. We can check these cases using only compare the x-coordinate and y-coordinate.



5. Source Code



Refers

Mark Berg, Otfried Cheong, Marc Kreveld, Mark Overmars, “Computational Geometry: Algorithms and applications 3rd”
JINSOL KIM, “벡터의 외적이란?”
mindo1103, “벡터의 외적(Cross Product)”
JINSOL KIM, “CCW(counter clockwise)”
SnowFleur, “[알고리즘] CCW(Counter Clock Wise)”
SnowFleur, “[알고리즘] CCW(Counter Clock Wise)”
Henu, “[백준 17387] 선분 교차 2 C++”