선분 교차 알고리즘

선분

> 직선 위에서 그 위의 두 점에 한정된 부분.

ex)

y = x 중 [(1,1) (3,3)]

 

참고 사이트

> 기본 지식

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

점 3개의 방향성을 나타내는 CCW

https://degurii.tistory.com/47

[알고리즘] CCW로 세 점의 방향성 판별하기

 

원래 풀려고 했던 문제

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

2162번: 선분 그룹

처음에 생각했던 방법

> 선분이 주어지면 그 선분을 가지고 있는 하나의 직선 방정식을 구한다.

> 직선 방정식의 교차점을 구하는 공식을 함수로 만든다.

> 그 교차점이 두 선분 위에 있는지 판단한다.

> 있다면 합치고 없다면 다음 그룹을 계사한다.

 

>>> 위와 같이 한다면 시간초과가 난다.

 

해결 방법

> 위에서 제시한 선분 교차 알고리즘(CCW)을 이용하여 두 선분이 교차한다면 같은 그룹으로 묶는다.

> 같은 그룹으로 묶는 과정은 유니온 파인드, 서로소 집합을 활용하면 될 듯 하다.

 

앞으로 할 일

> 선분 교차 알고리즘에 대해서 공부하고 특히, 벡터 관련 내용을 중점적으로 살펴보아야겠다.