[백준] 단계별로 풀어보기(단계:33, 기하2,JAVA)11758번, CCW

문제 링크

11758번: CCW

---

주의사항

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

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

---

문제 설명

---

 

접근 방법

기하란?

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

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

 

이 문제에 핵심은

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

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

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

 

처음 이 문제를 접근할 때 방향에 모든 경우를 구해서 구현하려고 하였지만 매우 비효율적이라고 느껴서 검색을 통해 구하는 방법을 찾아보았습니다.

 

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

[알고리즘] CCW로 세 점의 방향성 판별하기

 

해당 글에서 방향을 구하려면 신발끈 공식을 응용합니다.

 

점화식(신발끈 공식)

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

 

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

 

(x1, y1) , (x2, y2), (x3, y3) ..... (xn, yn)일 때

점화식 : |x1*y2 -x2*y1 + x2*y3 - x3*y2.....|/2

 

x1*y2 -x2*y1 + x2*y3 - x3*y2..... > 0 : 반시계(1)

x1*y2 -x2*y1 + x2*y3 - x3*y2..... = 0 : 일직선(0)

x1*y2 -x2*y1 + x2*y3 - x3*y2..... < 0 : 시계(-1)

 

예제입력1

(1, 1) ,(5, 5), (7, 3)

 

점화식 적용

1*5 - 5*1 + 5*3 - 7*5 + 7*1 - 1*3 = -16

 

-16 < 0

 

시계방향(-1) 출력

 

결과:  -1 출력

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 사용하여 3개의 좌표를 저장합니다.
• 신발끈 공식으로 방향을 구하는 cal함수를 실행하였습니다.
• BufferedWriter에 방향을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 신발끈 공식을 적용하여 방향을 반환합니다.

 

결과 코드

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

public class Main {
    static int[][] point = new int[3][2];	//3개의 좌표 저장 배열
    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;
        //3개 좌표 저장
        for(int i=0;i<3;i++){
            st = new StringTokenizer(br.readLine()," ");
            point[i][0] = Integer.parseInt(st.nextToken());
            point[i][1] = Integer.parseInt(st.nextToken());
        }
        int result = cal();		//방향 계산
        bw.write(result + "\n");	//방향 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    static int cal(){
    	//x1*y2 + x2*y3...의 합
        int sumA = point[0][0]*point[1][1] + point[1][0]*point[2][1] + point[2][0]*point[0][1];
        //x2*y1 + x3*y2...의 합
        int sumB = point[1][0]*point[0][1] + point[2][0]*point[1][1] + point[0][0]*point[2][1];
        int temp = sumA - sumB;
        if(temp>0)	//반시계
            return 1;
        else if(temp<0)	//시계
            return -1;
        else		//일직선
            return 0;
    }
}