볼록 껍질 썸네일형 리스트형 백준 3878번 - 점 분리 * 문제 링크 https://www.acmicpc.net/problem/3878 3878번: 점 분리 평면 위에 여러 개의 검정 점과 흰 점이 있다. 이때, 길이가 무한대인 직선을 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안 된다. 직선으로 인해서 나누어지는 두 그룹 www.acmicpc.net 문제 내용 요약 2차원 좌표 1사분면에 검정 점과 흰 점이 많이 있는데 (1 ≤ N,M ≤ 100) 얘네들을 직선 하나로 색깔별로 분리하려고 한다. 직선은 어떤 점도 만나면 안된다. 분리가 되는지 안 되는지 판단하자 (그림은 문제 링크 참고) 필요 배경 지식 두 가지 배경 지식이 필요하다. 컨벡스 헐과 선분 교차 판정 두 가지다. 이에 대한 기본적인 내용은 아래의 두 글을 참고하길 바.. 더보기 백준 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 ) 만큼 떨어지게, 모든 건물을 한 번에 두르게 지으면 길이가 얼마나.. 더보기 이전 1 다음
