3878번 - 점 분리
어느 부분에서 틀렸는지 감이 안잡힙니다...
우선, 전제는 "convex hull끼리 겹치지 않는다면 두 점 집합을 구분할 수 있다." 입니다.
따라서 가능한 종류는
1) convex hull들이 일부분 겹치는 경우
2) 한 convex hull이 다른 convex hull을 완전히 둘러싸는 경우
3) 어느 부분도 겹치지 않는 경우
로 구분하였고, 아래에서는 다음과 같이 확인했습니다.
: black convex와 white convex들을 이루는 선분 bi와 wj를 모두 비교하여 교차하는지 판별하였습니다.
--> 교차하면 NO 반환, 교차하지 않으면 다음 단계
: black과 white를 구분하지 않고 모든 점들을 이용해 만든 convex hull을 entire convex라고 할 때,
entire convex와 black / white convex 중 하나라도 일치하는 것이 있는지 확인하였습니다.
--> 있다면 NO 반환, 없다면 다음 단계
--> YES 반환
대체 어디서 잘못된 걸까요? ㅠㅠ
댓글을 작성하려면 로그인해야 합니다.
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 반환
대체 어디서 잘못된 걸까요? ㅠㅠ