선분 교차 3
면접 대비시간 제한0.25초메모리 제한512 MB
정수 좌표로 주어진 두 선분이 교차하는지 판정하고, 한 점에서 만나면 그 교점의 좌표를 출력한다.
문제
2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.
L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다.
입력
첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.
출력
L1과 L2가 교차하면 첫째 줄에 1, 아니면 0을 출력한다.
두 선분이 한 점에서 교차하는 경우 둘째 줄에 교차하는 점의 x좌표와 y좌표를 공백으로 구분해 출력한다. 한 점에서 교차하지 않는 경우에는 둘째 줄을 출력하지 않는다.
좌표의 절대/상대 오차는 10-9까지 허용한다.
제한
- -1,000,000 ≤ x1, y1, x2, y2, x3, y3, x4, y4 ≤ 1,000,000
- x1, y1, x2, y2, x3, y3, x4, y4는 정수
- 선분의 길이는 0보다 크다.