컨벡스 헐 썸네일형 리스트형 백준 3878번 - 점 분리 * 문제 링크 https://www.acmicpc.net/problem/3878 3878번: 점 분리 평면 위에 여러 개의 검정 점과 흰 점이 있다. 이때, 길이가 무한대인 직선을 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안 된다. 직선으로 인해서 나누어지는 두 그룹 www.acmicpc.net 문제 내용 요약 2차원 좌표 1사분면에 검정 점과 흰 점이 많이 있는데 (1 ≤ N,M ≤ 100) 얘네들을 직선 하나로 색깔별로 분리하려고 한다. 직선은 어떤 점도 만나면 안된다. 분리가 되는지 안 되는지 판단하자 (그림은 문제 링크 참고) 필요 배경 지식 두 가지 배경 지식이 필요하다. 컨벡스 헐과 선분 교차 판정 두 가지다. 이에 대한 기본적인 내용은 아래의 두 글을 참고하길 바.. 더보기 백준 3679번 - 단순 다각형 * 문제 링크 https://www.acmicpc.net/problem/3679 3679번: 단순 다각형 첫째 줄에 테스트 케이스의 개수 c (1 ≤ c ≤ 200)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 테스트 케이스의 첫 번째 숫자는 점의 개수 n (3 ≤ n ≤ 2000) 이다. 다음 숫자는 점의 좌 www.acmicpc.net 문제 내용 요약 주어진 점 N ( 3 ≤ N ≤ 2000 ) 개로 아무렇게나 다각형을 만들자 다각형의 선분은 무조건 점에서만 교차해야하고, 모든 점이 한 직선에 있는 경우는 없다. 접근법 계속해서 컨벡스 헐 문제를 풀어왔다면, 접근하기에 어렵지는 않을 것이다. 사실 컨벡스 헐까지 가지 않고, 각도에 따라 정렬할 줄만 알면 된다. 아래는 관련 배경 지식 링크.. 더보기 백준 7420번 - 맹독 방벽 * 문제 링크 https://www.acmicpc.net/problem/7420 7420번: 맹독 방벽 첫 번째 줄에 건물의 수 N과 거리 L이 주어진다. (3 ≤ N ≤ 1000, 1 ≤ L ≤ 1000, N과 L은 정수) 다음 N개의 줄에 거쳐 건물의 좌표 Xi와 Yi가 정수로 주어진다. (-10000 ≤ Xi, Yi ≤ 10000) 모든 건물의 좌 www.acmicpc.net 문제 내용 요약 화학 제국의 왕 성준이가 타국의 공격을 막으려고 건물들 ( 3 ≤ L ≤ 1000 ) 을 감싸는 맹독 방벽을 세우려 한다. 근데 만들기 힘들어서 최대한 적게, 그리고 자국민들 피해 안 가게 하려고 건물들에서 최소 L ( 1 ≤ L ≤ 1000 ) 만큼 떨어지게, 모든 건물을 한 번에 두르게 지으면 길이가 얼마나.. 더보기 백준 1708번 - 볼록 껍질 * 문제 링크 https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 문제 내용 요약 다각형의 아무 두 점을 잡아 선분을 그었을 때, 항상 다각형 내부에 존재하면 그 다각형을 볼록 다각형이라 한다. 2차원 평면에 N ( 3 ≤ N ≤ 100,000 ) 개의 점 중에 선택해서 모든 점들이 내부에 있도록 볼록 다각형을 만들었을 때 (Convex Hull) 의 선택한 점의 개수를 구해라. CCW (Counter Clockwise) 세 점.. 더보기 이전 1 다음
