kan5995   1년 전

어느 부분에서 틀렸는지 감이 안잡힙니다...

우선, 전제는 "convex hull끼리 겹치지 않는다면 두 점 집합을 구분할 수 있다." 입니다.

따라서 가능한 종류는 

1) convex hull들이 일부분 겹치는 경우 

2) 한 convex hull이 다른 convex hull을 완전히 둘러싸는 경우 

3) 어느 부분도 겹치지 않는 경우

로 구분하였고, 아래에서는 다음과 같이 확인했습니다.

1) convex hull들이 일부분 겹치는 경우

: black convex와 white convex들을 이루는 선분 bi와 wj를 모두 비교하여 교차하는지 판별하였습니다.

--> 교차하면 NO 반환, 교차하지 않으면 다음 단계

2) 한 convex hull이 다른 convex hull을 완전히 둘러싸는 경우 

: black과 white를 구분하지 않고 모든 점들을 이용해 만든 convex hull을 entire convex라고 할 때,

entire convex와 black / white convex 중 하나라도 일치하는 것이 있는지 확인하였습니다.

--> 있다면 NO 반환, 없다면 다음 단계

3) 어느 부분도 겹치지 않는 경우

--> YES 반환

대체 어디서 잘못된 걸까요? ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.