[백준/JAVA] 17387번: 선분 교차 2

🔺 문제

17387번: 선분 교차 2

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        // L₁
        long x1 = Integer.parseInt(st.nextToken());
        long y1 = Integer.parseInt(st.nextToken());
        long x2 = Integer.parseInt(st.nextToken());
        long y2 = Integer.parseInt(st.nextToken());
        
        // L₂
        st = new StringTokenizer(br.readLine()," ");
        long x3 = Integer.parseInt(st.nextToken());
        long y3 = Integer.parseInt(st.nextToken());
        long x4 = Integer.parseInt(st.nextToken());
        long y4 = Integer.parseInt(st.nextToken());        
        
        boolean cross = isCross(x1, y1, x2, y2, x3, y3, x4, y4);
        if(cross) System.out.println(1);
        else      System.out.println(0);
    }
    
    static int CCW(long x1, long y1, long x2, long y2, long x3, long y3) {
        long tmp = (x1*y2 + x2*y3 + x3*y1) - (x2*y1 + x3*y2 + x1*y3);
        
        if(tmp > 0)      return 1;  // 반시계
        else if(tmp < 0) return -1; // 시계
        else             return 0;  // 일직선
    }
    
    // 선분 겹침 여부 판별 함수
    // : 한 선분의 min 값이 다른 선분의 max값보다 클 때 안 겹침
    private static boolean isOverlap(long x1, long y1, long x2, long y2, long x3, long y3, long x4, long y4) {
        if(Math.min(x1, x2) <= Math.max(x3, x4) && Math.min(x3, x4) <= Math.max(x1, x2)
        && Math.min(y1, y2) <= Math.max(y3, y4) && Math.min(y3, y4) <= Math.max(y1, y2))
            return true;
        
        return false;
    }
    
    private static boolean isCross(long x1, long y1, long x2, long y2, long x3, long y3, long x4, long y4) {
        int abc = CCW(x1, y1, x2, y2, x3, y3);
        int abd = CCW(x1, y1, x2, y2, x4, y4);
        int cda = CCW(x3, y3, x4, y4, x1, y1);
        int cdb = CCW(x3, y3, x4, y4, x2, y2);
        
        // 선분이 일직선일 때
        if(abc * abd == 0 && cda * cdb == 0) {
            return isOverlap(x1, y1, x2, y2, x3, y3, x4, y4);   // 겹치는 선분인지 판별
        }
        // 선분이 교차할 때
        else if(abc * abd <= 0 && cda * cdb <= 0) {
            return true;
        }
        return false;
    }
}

✅ 해결 아이디어
✔ CCW를 이용한 선분 교차 여부 판정

 

 

---

🔺 다른 풀이들

- CCW 설명 굿!! & 변수 x,y를 Point 클래스에 저장해두고 쓰심.

[JAVA] CCW

 

 

- 그림 설명

[백준(Baekjoon)][자바(java)] 17387 : 선분 교차 2 / 기하

---

💬 느낀 점

이렇게 또 응용이 되는구나.... 신기

 

 

 

1회독	2회독	3회독	4회독	5회독
V	7/11

---

(참고)

CCW를 이용한 선분 교차 여부 판정 (2023-05-12 업데이트)