3878번: 점 분리 - 컨벡스 헐, CCW(선분 교차)
https://www.acmicpc.net/problem/3878 3878번: 점 분리평면 위에 여러 개의 검정 점과 흰 점이 있다. 이때, 길이가 무한대인 직선을 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안 된다. 직선으로 인해서 나누어지는 두 그룹www.acmicpc.net 0. 특정 색깔의 점이 아무것도 없는지 확인한다.1. 검은색 점, 흰색 점, 모든 점에 대한 컨벡스 헐을 만든다.2. 선분 교차를 통해 검은색 점의 컨벡스 헐과 흰색 점의 컨벡스 헐이 교차하는지 확인한다. 교차한다면 점이 분리되지 않는다.3. 한 컨벡스 헐 내에 다른 컨벡스 헐이 포함되는지 확인한다.#define _SILENCE_ALL_CXX20_DEPRECATION_WARNINGS#include us..
알고리즘/baekjoon
2023. 3. 8. 18:54
