문제
두 선분이 주어질 때, 두 선분이 교차하는지 판별하라. 끝점에서 만나는 경우는 없다.
입력
첫째 줄에 선분 1의 양 끝점 (x1, y1, x2, y2), 둘째 줄에 선분 2의 양 끝점 (x3, y3, x4, y4)이 주어진다. 좌표 절댓값은 1,000,000 이하.
출력
교차하면 1, 아니면 0을 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 1 5 5 1 5 5 1 | 1 |
풀이
CCW(Counter-Clockwise) 알고리즘을 4번 호출하여 두 선분의 교차 여부를 판별한다.
- CCW(P1, P2, P3): 세 점의 외적 부호로 방향(시계/반시계)을 판별한다
- 선분 AB와 CD가 교차하려면 두 조건을 모두 만족해야 한다
CCW(A, B, C) * CCW(A, B, D) < 0: C와 D가 AB의 양쪽에 위치CCW(C, D, A) * CCW(C, D, B) < 0: A와 B가 CD의 양쪽에 위치
핵심 아이디어: 두 선분이 교차하면 각 선분의 양 끝점이 상대 선분의 반대편에 위치한다. CCW 부호의 곱이 음수인지로 이를 O(1)에 판별할 수 있다.
코드
package day349;
import java.io.*;
import java.util.*;
public class Day336BOJ17386선분교차1 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int x3 = Integer.parseInt(st.nextToken());
int y3 = Integer.parseInt(st.nextToken());
int x4 = Integer.parseInt(st.nextToken());
int y4 = Integer.parseInt(st.nextToken());
char result = '0';
if (ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) < 0 &&
ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2) < 0)
result = '1';
bw.write(result + "\n");
bw.flush();
bw.close();
br.close();
}
public static int ccw(long x1, long y1, long x2, long y2, long x3, long y3) {
// CCW 공식 (x1y2+x2y3+x3y1)−(y1x2+y2x3+y3x1)
return x1 * y2 + x2 * y3 + x3 * y1 - y1 * x2 - y2 * x3 - y3 * x1 < 0 ? 1 : -1;
}
}복잡도
- 시간: O(1)
- 공간: O(1)