[BOJ/C] 11758번 문제풀이

문제 설명

2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다.

출력

P1, P2, P3를 순서대로 이은 선분이 반시계 방향을 나타내면 1, 시계 방향이면 -1, 일직선이면 0을 출력한다.

---

풀이 과정

우선 이 문제는 풀이를 열심히 봤는데도 문제가 잘 이해가 안가서 열심히 구글링해서 찾아봤다.

이 문제의 핵심은 ccw 알고리즘이라고 한다. ccw 알고리즘은 너무 생소해서 어떤 알고리즘인지 알아보았다.

 

 CCW 알고리즘 

반시계 방향 알고리즘으로, 평면 위에 놓여진 세 개의 점을 백터의 외적을 이용해서 방향 관계를 찾는 알고리즘

▶ 점 3개의 방향성을 나타냄

가능한 경우의 수는 반시계 방향, 시계 방향, 일직선로 총 3가지가 있다. 시계 방향을 -1, 일직선을 0, 반시계 방향을 1이라고 했을 때, P1은 검정색, P2는 초록색, P3을 파란색으로 나타내면 위 그림과 같다.

 

[참고자료]

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

https://comyoung.tistory.com/253

 

따라서 해당 부분을 참고하여 CCW 알고리즘 문제를 해결할 수 있었다.

사실 아직까지도 문제 이해가 되지 않아 나중에 기회가 되면 CCW 알고리즘을 활용한 다른 문제도 더 풀어보려 한다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

// ccw 알고리즘
int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    int temp = x1*y2+x2*y3+x3*y1;
    temp = temp - y1*x2-y2*x3-y3*x1;
    if (temp > 0) {
        return 1;
    } else if (temp < 0) {
        return -1;
    } else {
        return 0;
    }
}

int main(){
    int a,b,a1,b1,a2,b2;
    scanf("%d %d",&a,&b);
    scanf("%d %d",&a1,&b1);
    scanf("%d %d",&a2,&b2);
    printf("%d",ccw(a,b,a1,b1,a2,b2));
}