알고리즘
2022. 6. 4.
[Python] 20149 선분 교차 3 - 외적이 아닌 직선의 방정식으로
선분 교차여부를 따질 때 흔히 외적을 사용해 회전 방향으로 체크하곤 한다. 그런데 이 방법은 교점을 1개만 갖고 있는 경우를 구분하기가 상당히 까다롭다. 그래서 아예 직선의 방정식을 구해 교점을 구한 뒤 선분 위에 있는지 체크하였다. 1. 전처리 점의 위치가 무작위로 주어지기 때문에 사전식으로 정렬하여 경우의 수를 축소하였다. ax,ay,bx,by=I() cx,cy,dx,dy=I() A=(ax,ay) B=(bx,by) C=(cx,cy) D=(dx,dy) if A>B:A,B=B,A if C>D:C,D=D,C 2. 직선의 위치관계 판단 직선으로 경우의 수를 나눌 경우 매우 좋은 점이 바로 위치관계가 단순하다는 것이다. 평행 : 기울기가 같다. $\Delta x_{\overline{AB}}=bx-ax ,\De..