CCW 알고리즘 (선분 교차 판별)

CCW ( Counterclockwise) 말 그대로 시계 반대 방향이다.

외적을 이용하여 유도할 수 있다.

CCW알고리즘을 이용하여 세점의 방향성을 알 수 있다.

 

1. 반시계 방향인 경우

 

 

2. 시계 방향인 경우

 

 

 

3.세 점이 평행한 경우

 

 

출처: https://jason9319.tistory.com/358 [ACM-ICPC 상 탈 사람]

 

각각의 점을 A(x1, y1) , B(x2, y2), C(x3, y3) 이라고 좌표를 두고, A,B,C 순서로 방향관계를 구한다면,

CCW 함수의 return값은 x1y2 + x2y3 + x3y1 - (x2y1 + x3y2 + x1y3) 이 된다.(신발끈 공식과 같다)

RETURN값이 음수이면 시계방향.

양수이면 반시계방향.

0이면 세점이 평행하다. 

이 알고리즘을 이용하여 선분 교차 판별 문제를 풀어낼 수 있다.

선분교차판별

 

 

 

다음과 같은 경우의 CCW를 구해보면

C,D를 기준으로 A와 B의 CCW의 부호가 각각 다를 때

선분이 교차한다고 판단할 수 있다.

CCW(A,B,C)*CCW(A,B,D)<=0 일때.

 

 

그런데 위에 그림은 https://www.acmicpc.net/problem/12781 과 같은 범위가 정해져있는 문제에서 가능하다.

다음 그림을 보면 CCW값이 음수여도 교차하지 않는 경우이다.

 

 

이 그림을 보면 알 수 있는 것처럼 CCW(C,D,A)*CCW(C,D,B)<=0 이지만

선분이 교차하지 않는다.

다음과 같은경우는 

CCW(C,D,A)*CCW(C,D,B)<=0 이고 CCW(A,B,C)*CCW(A,B,D)<=0 둘다 만족해야 선분이 교차한다고 말할 수 있다.

 

 

 

 

하지만 선분의 교차에서 마지막 하나 더 고려해주어야할 점은

CCW(C,D,A)*CCW(C,D,B)==0 AND CCW(A,B,C)*CCW(A,B,D)==0 일 때 이다.

 

다음과 같은 경우에는 A,B와 C,D의 상대적 위치를 비교해 줘야한다. A,B둘중에 좌표가 큰값과 C,D중에 좌표가 큰값을 서로의 작은 값보다 클 때만 선분이 교차한다.

 

2162 선분 그룹

www.acmicpc.net/problem/2162

 

1.접근

집합을 만들고 선분의 교차 여부를 확인해야 하므로 CCW를 사용하여 유니온파인드로 합쳐준다

2.풀이

N(1≤N≤3,000)까지밖에 되지않으므로 for문을 두번 활용하여 서로 한번씩 CCW를 적용해본다.

3번째와 6번째를 비교하나 6번째와 3번째를 비교하나 똑같으므로 i는 n-1,j는 i+1~n까지 범위를 잡아준다.

집합의 크기를 구하려면 모든 cnt 집합의 원소 크기를 1로 초기화하고 병합해줄 때 마다 작은쪽으로 cnt를 더해주면 된다. 마지막 집합의 갯수는 경로압축을 사용해서 부모노드의 갯수만 계산하면 된다.(중복을 없애주는 set자료형 사용)

3.코드

4.배운점

• ccw의 값이 둘다 0일 때 좌표들의 크기를 비교하는 것이 생각하기 어려웠다. 교차하려면 당연히 한쪽 선분의 큰 좌표가 다른 선분의 작은좌표 이상이여야하고 반대쪽 선분의 큰좌표가 원래 선분의 작은좌표 이상이여야 한다는 걸 생각하기 어려웠다.
• parent 리스트가 당연히 경로압축이 다 된 리스트인 줄 알았는데 생각해보면 merge할 때만 find가 들어가므로 경로압축이 다 된것이 아니다. 착각했다. for문을 사용해서 전부 경로압축하고 set자료형을 썻더니 맞았다.

출처: https://jason9319.tistory.com/358 [ACM-ICPC 상 탈 사람]를 보고 공부하였습니다.