'볼록 껍질' 태그의 글 목록
본문 바로가기
728x90

볼록 껍질3

백준 No.7420 [맹독 방벽] BOJ No.7420 [맹독 방벽] 문제 7420번: 맹독 방벽 (acmicpc.net) 7420번: 맹독 방벽 첫 번째 줄에 건물의 수 N과 거리 L이 주어진다. (3 ≤ N ≤ 1000, 1 ≤ L ≤ 1000, N과 L은 정수) 다음 N개의 줄에 거쳐 건물의 좌표 Xi와 Yi가 정수로 주어진다. (-10000 ≤ Xi, Yi ≤ 10000) 모든 건물의 좌 www.acmicpc.net 설명 * 볼록 껍질 (컨벡스 헐 : Convex hull) 볼록 껍질을 응용하여 풀 수 있는 문제이다. 아래 예시를 들어 보았다. 건물들의 좌표를 위와 같이 입력을 해 보았다. 또한 해당 좌표들을 좌표평면에 표시 해 보았다. 위 좌표들을 모두 감싸면서 건물들에선 최소 L 만큼 떨어져 있어야 하는 방벽을 세워야 한다. .. 2022. 3. 28.
볼록 껍질 (컨벡스 헐 : Convex hull) 볼록 껍질 (컨벡스 헐 : Convex hull) 점들을 통해 볼록 다각형을 형성 다각형에 포함되지 않는 점들은 다각형 내부에 존재 참고 링크 2022.03.26 - [Algorithm (C++ based)/BOJ] - 백준 No.1708 [볼록 껍질] 백준 No.1708 [볼록 껍질] BOJ No.1708 [볼록 껍질] 문제 1708번: 볼록 껍질 (acmicpc.net) 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이.. johoonday.tistory.com 볼록 껍질(컨벡스 헐)의 기본 개념을 다루는 문제이다. 볼록 껍질(컨벡스 헐) 의 개념이 설명되어 있다. 2022. 3. 27.
백준 No.1708 [볼록 껍질] BOJ No.1708 [볼록 껍질] 문제 1708번: 볼록 껍질 (acmicpc.net) 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 설명 * 볼록 껍질 / 컨벡스 헐 (Convex hull) 볼록 껍질 위와 같이 평면 좌표에 N개의 점이 있을 때 점들을 이어 볼록 다각형을 만들면서, 잇지 않은 나머지 점들은 볼록 다각형 내부에 있도록 하는 것 이다. 볼록 껍질을 구현하기 위한 전처리 과정은 아래와 같이 정리할 수 있다. 1. 점들 중 껍질을 만들기 시작하는 점을 찾는다. - 보통 y값.. 2022. 3. 26.
728x90