[Python] 백준 17387 선분 교차 2

 

 

문제

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

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

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

 

 

 

 

 

난이도

골드 2

 

 

 

 

 

코드

import sys

def CCW(a1,b1,a2,b2,a3,b3) :
    ccw = (a2-a1) * (b3-b1) - (b2-b1) * (a3-a1)
    return ccw

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

abc = CCW(x1,y1,x2,y2,x3,y3)
abd = CCW(x1,y1,x2,y2,x4,y4)
cda = CCW(x3,y3,x4,y4,x1,y1)
cdb = CCW(x3,y3,x4,y4,x2,y2)

if abc * abd < 0 and cda * cdb < 0 :
    print(1)
elif abc == 0 and (min(x1,x2) <= x3 <= max(x1,x2) and min(y1,y2) <= y3 <= max(y1,y2)):
    print(1)
elif abd == 0 and (min(x1,x2) <= x4 <= max(x1,x2) and min(y1,y2) <= y4 <= max(y1,y2)):
    print(1)
elif cda == 0 and (min(x3,x4) <= x1 <= max(x3,x4) and min(y3,y4) <= y1 <= max(y3,y4)):
    print(1)
elif cdb == 0 and (min(x3,x4) <= x2 <= max(x3,x4) and min(y3,y4) <= y2 <= max(y3,y4)):
    print(1)
else :
    print(0)

 

 

 

 

 

 

풀이과정

처음으로 CCW 알고리즘에 대해 배웠다.

CCW 알고리즘은

세 점 A(x1,y1), B(x2,y2), C(x3,y3) 에 대해

CCW = (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1) 

값을 구하여

 

CCW > 0 : 반시계방향으로 배열

CCW < 0 : 시계방향

CCW = 0 : 일직선

 

이 원리를 사용하여

점 ABC, ABD 가 서로 다른 방향이고, CDA, CDB가 서로 다른 방향이면(곱이 음수이면) 두 선분이 교차한다고 판단한다.

일직선에 있는 경우는 CCW 값이 0이 나올텐데 그렇게 했을 때 하나의 선분 범위안에 다른 선분의 점이 존재하는지 판단하였다.

 

기하문제는 거의 처음푸는거 같은데 어렵다..