백준 17387번 선분 교차2 파이썬 골드2 기하

풀다 저세상 갈 뻔한 문제. 335명이라는 적은 정답률로 답지를 구할 수 없어 많이 울었다.

ccw 와 기하에 대한 감각이 있어야하는 문제였다.  

문제

2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있으면 교차하는 것이다.

L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다.

입력

첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.

출력

L1과 L2가 교차하면 1, 아니면 0을 출력한다.

제한

• -1,000,000 ≤ x1, y1, x2, y2, x3, y3, x4, y4 ≤ 1,000,000
• x1, y1, x2, y2, x3, y3, x4, y4는 정수

구현

x1, y1, x2, y2=map(int, input().split())
x3, y3, x4, y4=map(int, input().split())

answer=0
didanswer=False
def ccw(x1,y1,x2,y2,x3,y3):
    tmp= (x2-x1)*(y3-y1)- (x3-x1)*(y2-y1)
    if tmp> 0:
        return 1
    elif tmp < 0:
        return -1
    else:
        return 0
if ccw(x1,y1,x2,y2,x3,y3) * ccw(x1,y1,x2,y2,x4,y4)==0 and    ccw(x3,y3,x4,y4,x1,y1) * ccw(x3,y3,x4,y4,x2,y2)==0:
    didanswer=True
    if min(x1,x2)<=max(x3,x4) and min(x3,x4)<=max(x1,x2) and min(y1,y2)<=max(y3,y4) and min(y3,y4)<=max(y1,y2):
        answer=1
if ccw(x1,y1,x2,y2,x3,y3) * ccw(x1,y1,x2,y2,x4,y4)<=0 and    ccw(x3,y3,x4,y4,x1,y1) * ccw(x3,y3,x4,y4,x2,y2)<=0:
    if not didanswer:
        answer=1
print(answer)

        
    
    

참고문헌

[ ccw 개념 ] www.acmicpc.net/blog/view/27

[c++ 구현] imucoding.tistory.com/1060