문제 링크

성능 요약

메모리: 14264 KB, 시간: 108 ms

분류

많은 조건 분기, 기하학, 선분 교차 판정

제출 일자

2025년 2월 28일 19:59:58

문제 설명

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을 출력한다.

풀이

느낀점

• 애써 피해왔던 CCW 알고리즘,, 드디어 입문했다.
• 벡터가 뭔지, 외적이 뭔지도 몰라 가망이 없다고 생각했는데, 마주해봤다.
• 개념부터 잘 설명해주신 분이 계셔서 대략적인 개념들과 문제 풀이를 위한 공식의 원리 정도라도 이해해보고자 했다.

설계 : 60분 (공부시간까지)

• CCW(Counter ClockWise): 평면 위에 놓인 세 점의 방향관계를 알 수 있도록 하는 알고리즘
• (기하학에서의) 벡터: 크기와 방향을 가진 양을 나타내는 개념, 화살표로 나타내면 화살표의 길이가 크기, 화살표의 머리 방향이 방향이다.
  • 세 점 a, b, c 가 있을 때, a → b 인 벡터를 A, a → c 인 벡터를 B라고 해본다.
  • 벡터의 곱을 외적이라고 하는데, AXB 의 결과에 따라 A벡터를 기준으로 B벡터가 어느 방향에 있는지 판단할 수 있다.
    
  • 0보다 크면 시계 방향, 0보다 작으면 반시계 방향, 0이면 평행이다.
• 벡터의 외적을 활용하면 두 선분을 이루는 4개의 점을 사용해 선분 교차 여부를 판단할 수 있다.

  • 단, 두 점의 대소를 판단하는 기준이 일정하고, 그에 따른 A,B 벡터 순서가 일관성있어야 한다.

  • 나는 두 점에서 x의 값이 우선, x가 같다면 y값을 기준으로 대소비교를 했다. (왼쪽에 있을수록, 위쪽에 있을수록 작다)

    

  • 두 선이 교차하는 경우 한 선분의 점에서 다른 선분의 각 점으로 향하는 벡터의 곱이 서로 다른 것을 알 수 있다. (한 선분의 점은 두 점에 대해 모두 확인해야 한다.)

  • 만약 두 선분이 완전히 평행한 경우에는 4번의 외적 값이 모두 0일텐데, 이것은 위 조건에 부합하지 않는 예외 경우이다. 이 경우에는 각 점의 대소비교를 통해 판단한다.

    • 한 선분의 큰 점이 다른 선분의 작은 점보다 작아야 한다. (두 선분에 대해 모두 확인한다.)

코드(Java)

• 구현 시간: 60분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 선분 교차 2_17387
 * Date: 2025.02.28
 */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Line l1 = inputLine();
        Line l2 = inputLine();

        int res1 = ccw(l1.p1, l2.p1, l2.p2);
        int res2 = ccw(l1.p2, l2.p1, l2.p2);
        int res3 = ccw(l2.p1, l1.p1, l1.p2);
        int res4 = ccw(l2.p2, l1.p1, l1.p2);

        int answer = 0;
        if (res1 != res2 && res3 != res4) answer = 1;
        else if (res1 == 0 && res2 == 0 && res3 == 0 && res4 == 0) {
            if (l1.p2.compareTo(l2.p1) >= 0 && l2.p2.compareTo(l1.p1) >= 0) {
                answer = 1;
            }
        }

        bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
		br.close();
	}

    public static int ccw(Point a, Point b, Point c) {
        long[] v1 = {b.x - a.x, b.y - a.y, 0};
        long[] v2 = {c.x - a.x, c.y - a.y, 0};

        long result = v1[0] * v2[1] - v1[1] * v2[0];
        if (result > 0) return 1;
        else if (result < 0) return -1;
        return 0;
    }

    public static Line inputLine() throws Exception {
        st = new StringTokenizer(br.readLine(), " ");
        Point[] p = new Point[2];
        for (int j = 0; j < 2; j++) {
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            p[j] = new Point(x, y);
        }
        return new Line(p[0], p[1]);
    }
}

class Line {
    Point p1;
    Point p2;

    Line (Point p1, Point p2) {
        this.p1 = p1.compareTo(p2) <= 0 ? p1 : p2;
        this.p2 = p1.compareTo(p2) <= 0 ? p2 : p1;
    }
}

class Point implements Comparable<Point> {
    int x;
    int y;

    Point () {}
    Point (int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Point o) {
        if (this.x == o.x) return this.y - o.y;
        return this.x - o.x;
    }
}