[백준] 단계별로 풀어보기(단계:33, 기하2,JAVA)17386번, 선분 교차 1

문제 링크

17386번: 선분 교차 1

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

기하란?

도형의 성질, 모양 등을 연구하는 수학의 한 분야

기하학 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 좌표 3개가 주어진다.

2. P₁ -> P₂ -> P₃ 순으로 방향을 확인한다.

3. 반시계이면 1, 시계이면 -1, 일직선이면 0을 결과로 출력합니다.

 

처음 이 문제를 접근할 때 좌표에 대한 선분에 방정식을 구해서 두 선분이 교차하는지 확인하였지만 실패하였습니다.

 

어떻게 진행되는지 찾아보았는데 CCW를 사용하여 간단하게 판단할 수 있다는 것을 알게되었습니다.

 

제가 참고한 사이트입니다.

CCW / 두 선분의 교차 판단

 

신발끈 공식을 응용하여 교차하여 두 좌표로 이루어진 선분에 대하여 교차하는지 확인하였습니다.

※참고한 사이트에서는 일직선에 관한 부분도 고려하였지만 이 문제에서는 일직선에 입력 케이스가 나오지 않기 때문에 고려하지 않아도 됩니다.

 

점화식(신발끈 공식)

신발끈 공식 - 위키백과, 우리 모두의 백과사전

 

※신발끈 공식이 성립되려면 마지막에 첫 좌표가 저장되어야 합니다.!(중요!)

 

P1 = (x1, y1)

P2 = (x2, y2)

P3 = (x3, y3)

P4 = (x4, y4)

 

CCW(P1,P2,P3) * CCW(P1, P2, P4) < 0 && CCW(P3,P4,P1) * CCW(P3,P4,P2) < 0일 때

 

두 선분은 교차한다.

 

예제입력1

 

P1 : (1, 1)

P2 : (5, 5)

P3 : (1, 5)

P4 : (5, 1)

 

CCW(P1, P2, P3) 

1*5 - 5*1 + 5*5 - 1*5 + 1*1 - 1*5 = 16

 

CCW(P1, P2, P4) 

1*5 - 5*1 + 5*1 - 5*5 + 5*1 - 1*1 = -16 

 

CCW(P3, P4, P1) 

1*1 - 5*5 + 5*1 - 1*1 + 1*5 - 1*1 = -16

 

 

CCW(P3, P4, P2) 

1*1 - 5*5 + 5*5 - 5*1 + 5*5 - 1*5 = 16

 

점화식 적용

 

CCW(P1,P2,P3)*CCW(P1,P2,P4) = -256 < 0

CCW(P3,P4,P1)*CCW(P3,P4,P2) = -256 < 0

 

둘 다 음수이기 때문에 두 선분은 교차한다.

 

결과:  1 출력

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 사용하여 4개의 좌표를 저장합니다.
• ccw함수를 이용해서 선분이 교차하는지 확인하였습니다.
• BufferedWriter에 선분이 교차하면 1, 교차하지 않으면 0을 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• ccw함수는 신발끈 공식을 적용하여 양수인지 음수인지 확인하여 반환합니다.

※좌표의 최대값이나 최소값이 1,000,000 or -1,000,000이기 때문에 long자료형을 사용해주셔야 합니다!

 

결과 코드

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

public class Main {
	//좌표 관련 클래스
    static class point{
        long x,y;
        public point(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }
    static point[][] point = new point[2][2];
    static public void  main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        StringTokenizer st;
        //입력되는 좌표 저장
        for(int i=0;i<2;i++){
            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());
            point[i][0] = new point(x1,y1);
            point[i][1] = new point(x2,y2);
        }
        //교차하는지 CCW로 확인하기
        if(ccw(point[0][0], point[0][1],point[1][0])*ccw(point[0][0], point[0][1],point[1][1]) < 0 &&
            ccw(point[1][0], point[1][1],point[0][0]) * ccw(point[1][0], point[1][1],point[0][1])<0)
            bw.write("1");		//교차할 때
        else
            bw.write("0");		//교차하지 않을 때
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //신발끈 공식 응용한 함수
    static int ccw(point P1, point P2, point P3 ){
        long sumA = P1.x*P2.y + P2.x*P3.y + P3.x*P1.y;
        long sumB = P1.y*P2.x + P2.y*P3.x + P3.y*P1.x;
        if(sumA-sumB<0)		//음수이면 -1 반환
            return -1;
        else		//양수이면 +1 반환
            return 1;

    }
}