컨벡스헐 (1) 썸네일형 리스트형 [기타/알고리즘] 서로 다른 색의 두 점의 쌍 구하기(컨벡스 헐) 해당 문제는 학교 과제로 받은 문제이다. 문제의 요지는 빨간색점과 파란색점이 서로 교차하지않고 선을 그어야 한다. 처음에는 어떻게 해야할지 몰라 이리 저리 고민하다 컨벡스 헐 알고리즘이란 것을 발견하여 포스팅 하고자 여기에 쓴다. 이 문제는 최외곽의 점을 찾아 해당 점에서 반시계방향(시계방향으로 하여도 상관없음)회전하며 선을 차례대로 그었을때 해당 선에 의해서 나누어 지는 면에 속하는 파란색 점과 빨간색 점의 수를 동일하다면 그 때 선을 그어주고 분할정복기법을 이용해서 왼쪽 영역과 오른쪽 영역으로 나누어 각각 다시 분할정복을 수행해준다. import java.io.*; import java.nio.charset.StandardCharsets; import java.util.Arrays; import ja.. 이전 1 다음
