문제
두 선분이 주어질 때, 두 선분이 교차하는지 판별하라. 선분 교차 1과 달리 끝점에서 만나거나 일직선 위에서 겹치는 경우도 교차로 판정한다.
입력
첫째 줄에 선분 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 알고리즘으로 교차를 판별하되, 세 점이 일직선인 경우(CCW=0)에는 좌표 범위 겹침을 추가로 확인한다.
- 네 점에 대해 CCW(P1,P2,P3), CCW(P1,P2,P4), CCW(P3,P4,P1), CCW(P3,P4,P2)를 계산한다
- 네 CCW 값 중 일부가 0인 경우(일직선): x좌표와 y좌표의 범위가 서로 겹치는지 확인한다
- 일직선이 아닌 경우: CCW(P1,P2,P3)*CCW(P1,P2,P4) ≤ 0 && CCW(P3,P4,P1)*CCW(P3,P4,P2) ≤ 0이면 교차
- 좌표 값이 크므로 long 타입으로 외적을 계산하여 오버플로를 방지한다
핵심 아이디어: 선분 교차 1과 달리 CCW가 0인 경우(일직선)를 별도로 처리해야 한다. 이때는 두 선분의 x, y 범위가 겹치는지 확인하여 교차를 판별한다.
코드
package day349;
import java.io.*;
import java.util.*;
public class Day336BOJ17387선분교차2 {
static class Point {
long x, y;
public Point(long x, long y) {
this.x = x;
this.y = y;
}
}
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;
Point[] point = new Point[4];
long x1, y1, x2, y2, x3, y3, x4, y4;
st = new StringTokenizer(br.readLine());
x1 = Long.parseLong(st.nextToken());
y1 = Long.parseLong(st.nextToken());
x2 = Long.parseLong(st.nextToken());
y2 = Long.parseLong(st.nextToken());
st = new StringTokenizer(br.readLine());
x3 = Long.parseLong(st.nextToken());
y3 = Long.parseLong(st.nextToken());
x4 = Long.parseLong(st.nextToken());
y4 = Long.parseLong(st.nextToken());
point[0] = new Point(x1, y1);
point[1] = new Point(x2, y2);
point[2] = new Point(x3, y3);
point[3] = new Point(x4, y4);
bw.write(checkCCW(point) + "\n");
bw.flush();
bw.close();
br.close();
}
public static int checkCCW(Point[] p) {
boolean is_result = false;
int result = 0;
int p123 = ccw(p[0], p[1], p[2]);
int p124 = ccw(p[0], p[1], p[3]);
int p341 = ccw(p[2], p[3], p[0]);
int p342 = ccw(p[2], p[3], p[1]);
boolean compare1 = Math.min(p[0].x, p[1].x) <= Math.max(p[2].x, p[3].x);
boolean compare2 = Math.min(p[2].x, p[3].x) <= Math.max(p[0].x, p[1].x);
boolean compare3 = Math.min(p[0].y, p[1].y) <= Math.max(p[2].y, p[3].y);
boolean compare4 = Math.min(p[2].y, p[3].y) <= Math.max(p[0].y, p[1].y);
if (p123 * p124 == 0 && p341 * p342 == 0) {
is_result = true;
if (compare1 && compare2 && compare3 && compare4)
result = 1;
}
if (p123 * p124 <= 0 && p341 * p342 <= 0) {
if (!is_result)
result = 1;
}
return result;
}
public static int ccw(Point p1, Point p2, Point p3) {
// CCW 공식 (x1y2+x2y3+x3y1)−(y1x2+y2x3+y3x1)
long result = ((p1.x * p2.y) + (p2.x * p3.y) + (p3.x * p1.y)) - ((p1.y * p2.x) + (p2.y * p3.x) + (p3.y * p1.x));
if (result > 0) // 반시계
return 1;
else if (result == 0) // 일직선
return 0;
else // 시계
return -1;
}
}복잡도
- 시간: O(1)
- 공간: O(1)