[백준]_11758번 : CCW(파이썬 and C언어)

11758번: CCW

제목 그대로 ccw알고리즘 저격 문제이다. 심지어 ccw알고리즘을 구현하기만 하면 해결되는 문제이기 때문에 ccw가 무엇인지만 알고 있으면 그렇게 어려운 문제는 아니다. 질문 게시판에서 보이는 ccw를 사용하지 않은 풀이를 보니 왜 알고리즘을 공부해야 하는지 깨닫게 되었다. 

 

전략

ccw는 Counter Clock Wise알고리즘을 뜻한다. ccw알고리즘은 복잡한 코드 대신 외적을 사용하여 세 점의 위치 관계를 파악할 수 있게 해준다. 정확한 원리는 ▷여기에서

 

이제 우리가 해줘야 할 일은 P1과 P2를 이은 벡터(a)와 P1과 P3를 이은 벡터(b)를 이용해 외적 연산을 해주면 된다. 세 점 사이의 관계를 다룸에 있어 왜 외적이 필요할까?

 

문제에서는 P1, P2, P3 순서대로 어떤 회전 동향을 갖고 있는지 물어보고 있다. 그렇다면 a벡터를 기준으로 했을 때 b벡터의 상대적 위치(왼쪽, 오른쪽, 같은 방향)가 회전 동향의 정보를 내포하고 있음을 알 수 있다. 오른팔(a벡터)을 앞으로 뻗은 상태에서 왼팔을 P3를 향해(b벡터) 뻗어보자. 오른손 법칙에 의해 만약 오른팔과 왼팔이 교차하지 않으면(b벡터가 a벡터에 대해 왼쪽에 존재할 때 == 외적값 양수 == 반시계 동향) 1을 출력하고 오른팔과 왼팔이 교차하면(b벡터가 a벡터에 대해 오른쪽에 존재할 때 == 외적값 음수 == 시계 동향) -1을 출력하고 마지막으로 오른팔과 왼팔이 같은 방향을 가리키고 있으면(b벡터와 a벡터가 같은 방향을 가리킴 == 외적값 0 == 일직선 동향) 0을 출력하면 되는 것이다.    

---

시도 1(Python)

import sys

input = sys.stdin.readline
x1, y1 = map(int, input().split())
x2, y2 = map(int, input().split())
x3, y3 = map(int, input().split())

def ccw(x1, x2, x3, y1, y2, y3):
    if (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) < 0:
        return -1
    elif (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) > 0:
        return 1
    return 0

print(ccw(x1, x2, x3, y1, y2, y3))

시도 2(C언어)

#include <stdio.h>
#include <stdlib.h>
int ccw(int x1,int x2,int x3,int y1,int y2,int y3){
    if(((x2-x1)*(y3-y1)-(y2-y1)*(x3-x1))<0) return -1;
    else if((x2-x1)*(y3-y1)-(y2-y1)*(x3-x1)==0) return 0;
    return 1;
}
int main(){
    int x1,x2,x3,y1,y2,y3;
    scanf("%d %d", &x1,&y1);
    scanf("%d %d", &x2,&y2);
    scanf("%d %d", &x3,&y3);
    printf("%d", ccw(x1,x2,x3,y1,y2,y3));
}