[Java] 기하학 (CCW)

https://www.acmicpc.net/problem/11758

11758번: CCW

 

다시 한번 내 머리가 좋지 않다는 것을 깨닫게 해 준 문제.

애초에 종이랑 펜 없이 머리만 굴려서 절대 풀 수 없었다.

여차저차 나름대로 풀이법을 생각해서 돌려봤지만 4연 실패를 안겨주었다.

 

뭐가 문제였을까 찾아본 결과 아무리 double형이라도 그 수가 크다면 부동 소수점 정밀도 문제가 생겨 틀리는 경우가 있다고 했다. 전공자 주제에 이런 건 생각지도 못한 변수였다. 당연히 double을 쓰면 실수의 나눗셈이 정확하게 떨어질 것이라고 생각했었는데 그게 아니었던 것이다.

 

그래도 푼 게 아까우니까 일단 내가 풀었던 코드를 올려놔야지. 아마 부동 소수점 문제가 아니라 다른 게 문제일 수 도 있을 수도 있다.

 

public class Main {

    static double[][] xy = new double[3][2];
    static double first_radian, second_radian;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        for(int i=0; i<3; i++){
            st = new StringTokenizer(br.readLine());
            xy[i][0] = Double.parseDouble(st.nextToken());
            xy[i][1] = Double.parseDouble(st.nextToken());
        }


        setFirst_radian();
        setSecond_radian();

        if(second_radian == first_radian) System.out.println(0); //기울기가 같으면 직선
        else if ((Math.PI-second_radian) == first_radian) System.out.println(0);
        else if ((Math.PI+second_radian) == first_radian) System.out.println(0);
        else if( second_radian >first_radian ) { //second_radian이 first_radian 보다 크고 first_radian+180도 보다 작으면 CCW
            System.out.println(1);
        }
        else {//CW
            System.out.println(-1);
        }

    }

    static public void setFirst_radian(){
        if(xy[1][0] == xy[0][0]) {first_radian = Math.PI/2; return;}


        first_radian = (xy[1][1]-xy[0][1]) / (xy[1][0]-xy[0][0]);

        if(first_radian<0 && ( (xy[1][1]-xy[0][1]) >  0) ) first_radian = Math.PI+first_radian; //2사분면
        else if(first_radian>0 && ( (xy[1][1]-xy[0][1]) <  0)) first_radian = Math.PI+first_radian; //3사분면
      
    }

    static public void setSecond_radian(){
        if(xy[2][0] == xy[1][0]) {second_radian = Math.PI/2; return;}

        second_radian = (xy[2][1]-xy[1][1]) / (xy[2][0]-xy[1][0]);

        if(second_radian<0 && ( (xy[2][1]-xy[1][1]) >  0) ) second_radian = Math.PI+second_radian; //2사분면
        else if(second_radian>0 && ( (xy[2][1]-xy[1][1]) <  0)) second_radian = Math.PI+second_radian; //3사분면
     
    }

}

 

 

해당 문제 풀이법을 찾아보니 이미 정형화된 기하학 필수 문제였었고 공식까지 존재했었다.

대체 이따위 근본 없는 공식은 어떻게 유도된 걸까. 유도하지 않고 공식을 쓰는 걸 굉장히 싫어하기 때문에 공식을 한번 증명해 보자. - 증명 실패함 진짜 이거 어떻게 나온 거냐? 아마 벡터 내적 외적 뭐 그런 거 같은데 고등학교 기벡 배운 지 어언 5년 대학교 선행대수학 배운 지 어언 4년이 지난 지금 1도 모르겠다. 

 

 

 

class Point{
    int x,y;

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

    static int x,y;
    static Point[] point = new Point[3];
    static int result;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        for(int i=0; i<3; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            point[i] = new Point(x, y);
        }

        result = (point[0].x * point[1].y) +  (point[1].x * point[2].y) +  (point[2].x * point[0].y) -
                (  (point[1].x * point[0].y) +  (point[2].x * point[1].y) +  (point[0].x * point[2].y) );

        if(result==0) System.out.println(0);
        else if (result>0)  System.out.println(1);
        else System.out.println(-1);

    }

}

 

아래 참고하자 

 

https://www.acmicpc.net/blog/view/27

점 3개의 방향성을 나타내는 CCW