본문 바로가기

볼록 껍질

 (3)
[Python] 3878번 점 분리 https://www.acmicpc.net/problem/3878 23/10/06  이전에 볼록 껍질 문제를 쭉 푼 적이 있었는데, 그 때 해결 했던 문제 중 하나이다. 흥미로운 문제라고 생각되어 기록으로 남겨보고자 한다. 문제 접근 방식:  문제의 요구 사항은 검은 점과 흰 점을 오직 하나의 직선만으로 서로 분리할 수 있는지 판단하는 것이다. 검은 점끼리를 고무줄로 감싸고, 흰 점끼리를 고무줄로 감쌌을 때, 두 고무줄이 겹치지 않으면 가능하다고 판단했다. 여기서 볼록껍질이라는 말을 사용하지 않은 이유는 고무줄이라는 용어가 더 적합하다고 생각했기 때문이다. 볼록껍질은 고무줄이라는 말을 온전히 대변하지 않는다. 예를 들어, 두 점만 있는 경우 볼록 껍질을 정의하기가 어려운데, 고무줄은 정의할 수 있다. 한..
[Python] 1708번 볼록 껍질 https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 23/10/02 기하 알고리즘 중 대표적인 알고리즘, 볼록 껍질 알고리즘을 연습할 수 있는 좋은 문제이다. 이 문제를 통해 볼록 껍질을 구현하는 템플릿 코드를 구성하면 좋을 것이다. 문제 접근 방식: 일반적으로 볼록 껍질을 구현하는 데에는 두 가지 방법이 존재한다. 이 문제의 해설에서는 두 가지 방법 모두 소개할 것이다. 첫번째 방법은 그라함 스캔이다. 그라함 스캔의 원리는 간..
CCW 알고리즘(CCW Algorithm) 최근에 배우게 된 CCW 알고리즘에 대해 글을 써보고자 한다. CCW 알고리즘이란? Counter-ClockWise의 줄임말로, 직역하면 반시계 방향이라는 뜻임. 세 점 p1, p2, p3가 주어져 있고, 이 세 점을 p1, p2, p3 순서대로 직선으로 이었을 때, 시계방향으로 휘어지는가, 반시계 방향으로 휘어지는가, 혹은 일직선을 이루는가를 판별하는 알고리즘. 방향이 중요하기 때문에 벡터의 개념을 알아야 함. 이 알고리즘을 활용하여 다양한 기하학 알고리즘에 적용할 수 있음. 대표적으로 선분 교차 판정 알고리즘, 볼록 껍질 알고리즘(컨벡스 헐) 등이 있음. 요약된 내용으로만 보아서는 무슨 뜻인지 잘 모를 수도 있을 것이다. 그래서 다음과 같이 그림을 준비했다. 위의 그림처럼 세 점 P1, P2, P3를..

티스토리툴바