Dev_Diary

https://www.acmicpc.net/problem/4225볼록 껍질 문제의 응용입니다.도형이 통과할 수 있는 구멍의 최솟값을 구하라는 것은 도형의 폭 중 가장 작은 값을 찾으라는 말과 같습니다.그렇다면 도형의 폭의 최솟값은 어떻게 구해야 할까요? 1. 볼록 껍질에 속해있는 점들 사이의 거리?결론부터 말하자면 아닙니다.붉은 선이 점들을 이은 선입니다.붉은 선도 폭들의 하나이긴 하지만 하늘색 선에 비하면 길이가 긴 것을 알 수 있습니다. 2. 변에서 점 사이의 거리그림에서 힌트가 나와있습니다.볼록 껍질에 속하는 변에서 볼록껍질에 속하는 점 까지의 거리들 중 최댓값이 해당 변에서 측정한 도형의 폭 이라고 할 수 있습니다.  즉 변에서 점 사이의 거리들의 최댓값 중 최솟값을 찾으면 폭의 최솟값을 찾을 수..

https://www.acmicpc.net/problem/1027 현재 서있는 건물 꼭대기에서 다른 건물을 볼 수 있는 조건은 내가 서있는 건물과 보고자 하는 건물 사이의 건물들이 시야를 가리지 않는 것입니다. 즉 서있는 건물의 꼭대기와 보고자 하는 건물의 꼭대기를 이은 선분이 다른 건물과 교차하지 않으면 됩니다. 다만 이런 식으로 진행하면 앞선 건물이 다음 건물을 가리는 경우를 고려할 수 없으니 다른 방법을 생각해야 합니다. 왼쪽에 있는 건물의 왼쪽에 있는 건물을 보려면 내가 서있는 건물의 꼭대기에서 가까운 왼쪽에 있는 건물의 꼭대기를 향해 반직선을 그었을 때 반직선의 반시계 방향에 건물의 꼭대기가 있다면 이 건물은 앞선 건물에 가려 보이지 않습니다. 반대로 반직선의 시계 방향에 건물의 꼭대기가 있다면..

https://www.acmicpc.net/problem/2254 2254번: 감옥 건설첫째 줄에 N(1 ≤ N ≤ 1,000), Px, Py (-100,000 ≤ Px, Py ≤ 100,000)이 주어진다. 다음 N개의 줄에는 차례로 담 기둥의 좌표가 주어진다. 각각의 좌표는 절댓값이 100,000을 넘지 않는 정수이다.www.acmicpc.net볼록 껍질 ( convex hull ) 알고리즘과 임의의 점이 다각형 안에 존재하는지 찾는 알고리즘을 함께 사용하면 풀 수 있습니다. 볼록 껍질 알고리즘은 아래 링크를 C++" data-og-description="https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 ..

https://www.acmicpc.net/problem/1688 1688번: 지민이의 테러 첫째 줄에 방어막의 꼭짓점의 개수 N(3 ≤ N ≤ 10,000)이 주어진다. 이어서 N개의 줄에는 꼭짓점들의 좌표가 순서대로 주어진다. 시계방향으로 주어질 수도 있고, 반시계방향으로 주어질 수도 있다 www.acmicpc.net 일반적인 볼록 다각형이라면 단순히 모든 직선과 사람의 좌표를 CCW 알고리즘을 통해 일관된 방향이 나오는지 체크하면 되지만 오목 다각형을 포함하는 문제라면 그렇게 쉽게 풀리지 않습니다. (0, 0) 에서 출발해서 시계 방향으로 체크한다고 가정하겠습니다. 0~3 직선까지는 직선-점의 방향이 시계방향이지만 4 직선에서는 반시계방향인 것을 알 수 있습니다. 즉 오목 다각형을 포함하는 문제에서..

https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net 선분이 교차하는지 판단하는 알고리즘과 그룹을 판단하기 위한 유니온 파인드 알고리즘을 함께 사용하면 풀 수 있습니다. 우선 선분이 교차하는지 판단하기 위해 두 개의 선분이 주어졌을 때 가질 수 있는 상태를 생각해보겠습니다. 위와 같이 열 가지의 상태가 존재하며 모든 상태를 고려해주겠습니다. 상태의 파악에는 CCW 알고리즘을 사용하겠습니다. (0, 0) 의 경우에는 ..

https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 볼록 껍질, 즉 Convex Hull 문제입니다. 이 문제를 푸는 방법 중 보편적으로 알려져 있는 알고리즘은 그라함 스캔, 그라함 알고리즘으로 알려져 있습니다. 해당 알고리즘으로 문제를 풀어보겠습니다. 그라함 스캔을 사용하기 위해서는 CCW 알고리즘을 알아야 하는데, 외적을 이용하는 알고리즘으로 세 개의 점의 상태를 알 수 있습니다. 즉 세 개의 점이 하나의 직선 위에 있는지 ..

https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 백준 11758 Python https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수..

https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net CCW 알고리즘을 사용하면 쉽게 풀 수 있습니다. import math def solution(data_list): # x, y 좌표 분리 x_list = [] y_list = [] for x, y in data_list: x_list.append(x) y_list.append(y) x_list.append(data_list[0]..