백준 17386번: 선분 교차 1

백준 17386번: 선분 교차 1

x1,y1,x2,y2 = map(int,input().split())
x3,y3,x4,y4 = map(int,input().split())
if(x1>x2):
    x1,x2 = x2,x1
    y1,y2 = y2,y1
if(x3>x4):
    x3,x4 = x4,x3
    y3,y4 = y4,y3
#L1: (x1,y1) <-> (x2,y2)
#L2: (x3,y3) <-> (x4,y4)

if(x2!=x1 and x4!=x3):
    m1 = (y2-y1)/(x2-x1)
    m2 = (y4-y3)/(x4-x3)
    if(m1!=m2):
        x_cor = (m1 * x1 - y1 - m2 * x3 + y3) / (m1 - m2)
        if(x1<=x_cor<=x2 and x3<=x_cor<=x4):
            print(1)
        else:
            print(0)
    else:
        print(0)
else:
    #하나 or 둘 다 가 수직임.
    if(x2==x1 and x3==x4):
        if(x2==x3): #동일한 수직선
            print(1)
        else:
            print(0) #둘 다 수직, 만날 수 없다.
    else:
        if(x2==x1): #L1이 수직
            m2 = (y4 - y3) / (x4 - x3)
            if(x3<=x2<=x4 and y1<=m2*(x2-x3)+y3<=y2): #L2의 범위가 L1 수직을 지나가고, L2에서 L1 수직 x의 교점이 L1의 범위 이내다.
                print(1)
            else:
                print(0)
        elif(x3==x4): #L2가 수직
            m1 = (y2 - y1) / (x2 - x1)
            if(x1<=x3<=x2 and y3<=m1*(x3-x1)+y1<=y4):
                print(1)
            else:
                print(0)

그냥 직선의 방정식 구한 후에 교점이 범위 내에 있는지 찾아주는 방식 + y축에 수직한 선분인 예외상황을 고려해주면 풀 수 있는 문제다. 단, x1<=x2, x3<=x4라는 보장이 없으므로 이 부분은 입력 받은 후에 수정해줘야한다. (처음에 이걸 고려 안해서 틀렸다.)
단순한 문제인데 골드여서.. 시간 제한이 0.25초길래 직선의 방정식으로 하면 시간초과가 나나? 했는데 그것도 아니었다. (python3 기준 44ms로 통과한다.)

찾아보니 이 문제를 CCW라는 알고리즘으로 풀 수 있다고 한다. 이름이 뭔가 복잡해 보이지만 그냥 외적이다..
외적의 개념을 안다면 당연하지만, 3개의 점을 이은 직선의 방향이 시계방향이면 결과가 음수, 직선이면 0, 반시계방향이면 결과가 양수이다. (잘 모르겠으면 물리에서 오른 나사 법칙 했던 걸 생각해보면 된다.)

L1의 양 끝점을 A, B. L2의 양끝점을 C, D라고 할때 AB와 C의 외적<->AB와 D의 외적, CD와 A의 외적<->CD와 B의 외적이 동시에 만족해야한다. (만나지 않는다면, 방향이 똑같은 경우가 생긴다.) 따라서 CCW(x1,y1,x2,y2,x3,y3)*CCW(x1,y1,x2,y2,x4,y4)<0이고 CCW(x3,y3,x4,y4,x1,y1)*CCW(x3,y3,x4,y4,x2,y2)<0인 경우는 결과가 1이고 그렇지 않으면 결과가 0인 것으로 구현하면 된다.
외적이 0인 경우는 직선, 즉 일직선인 경우이다. 하지만 문제상에서 세 점이 일직선 위에 있는 경우는 없다고 했다. 따라서 고려해주지 않아도 된다.

CCW로 풀면 빠르게 풀 수 있고, 시간을 단축할 수는 있다. 코딩테스트같이 시간이 제한적일때 사용할 수 있겠다. (하지만 코딩테스트에서 수학 문제가 나올지는 잘 모르겠다... 내 경험상 수학 문제가 나온 기억은 딱히 없다..) 하지만 CCW가 아니어도 풀 수 있는 문제니.. CCW의 개념은 그냥 알아만 놓는 정도로 넘어가도 될듯하다.