백준/기하 (5) 썸네일형 리스트형 [ICPC] 백준 3861 - Slalom https://www.acmicpc.net/problem/3861 아이디어 최단 경로는 변위가 작은, 다시 말해 가능한 한 회전을 하지 않을 때 성립한다. 조금 쉬운 예시로 다음 그림을 보면 좋다. 꺾지 않는 최장 직선 찾기 그러면 우리는 한 직선 이동에 게이트를 많이 지나는 방법을 찾아야 한다. 그러기 위해 우리는 다음 고려할 것이다. 어떤 게이트 끝점에서 직선으로 최대한 도달할 수 있는 게이트는 어디인가? 좀 더 생각하면 반드시 회전을 해야만 할 때 탐욕적으로 다음 게이트의 끝점에만 가면 됨을 알 수 있다. 이 사실을 통해 우리는 어떤 게이트의 끝점(시작점 포함)에서 출발할 때 다음 게이트의 끝점을 경유해야만 하는지, 그렇지 않아도 다음 게이트를 통과할 수 있는지 검사하면 충분하다는 생각을 할 수 있.. [ICPC] 백준 9015 - 정사각형 https://www.acmicpc.net/problem/9015 아이디어 정사각형은 네 변의 길이가 같고 내각의 크기가 전부 90도이다. 각은 크게 신경 쓰지 않고 일단 두 점이 있을 때 정사각형을 하나 결정한다고 생각해보자. 그러면 아래와 같은 경우를 생각할 수 있다. 두 점을 선택했을 때 오른쪽 위에 정사각형을 만족시키는 두 점이 있는가?로 문제를 좁힐 수 있다. 그런데 정사각형을 만족시키는 두 점을 어떻게 선택할까? 두 점의 y 거리와 x 거리를 생각하면 알 수 있다. P2의 좌표에서 P1의 좌표를 뺀 값을 dx, dy라고 했을 때 위 그림처럼 선택한 두 점에서 x에 dy를 빼고 y에 dx를 더한 좌표에 점이 있는지 확인하면 된다. P2에서 P1을 뺀 것이므로 dy는 음수임을 명심하자. 이렇게 구.. 백준 2022 - 사다리 https://www.acmicpc.net/problem/2022 사전 지식 본인은 이 문제를 삼분 탐색으로 풀었다. 그 외에도 풀이를 이해하기 위해선 중학교 수준의 기하 지식과 비례식에 대한 이해가 필요하다. 풀이 구하려는 밑변의 길이를 $z = a + b$라고 두자. 그리고 x와 y는 다음과 같이 정리가 가능하다. 하지만 z의 길이를 모르는데 a, b를 구할 수 없다. 우리는 z를 구하는 대신 건물 벽에 접촉한 지점의 높이에 해당하는 옆변의 길이 $w_{x}$, $w_{y}$를 구할 것이다. 이렇게 $w_{x}$와 $w_{y}$를 꺼내면 $w_{x}$와 c, 그리고 $w_{y}$와 c는 각각 $a:a+b = c:w_{y} \; (b:a+b = c:w_{x})$의 비례식으로 표현이 가능함을 발견할 수 .. 백준 1064 - 평행사변형 icpc.me/1064 아이디어 학창 시절에 배운 평면의 결정 조건을 기억하는가? 평면의 결정 조건 중에는 이런 것이 있다. 한 직선 위에 있지 않은 세 점 평면이 아닌 공간 위에서는 당연히 평면도형 또한 생겨날 수 없으므로 평행사변형이 만들어질 수 없는 경우를 결정할 수 있다. 1. 주어진 세 점이 한 직선 위에 있는 경우 2. 주어진 세 점의 좌표가 모두 동일할 경우 이 두가지의 경우 평면 도형을 만들 수 없으므로 -1을 출력해주는 조건이 된다. 그렇다면 나머지의 경우는 어떻게 될까? 한 점을 자유롭게 놓을 수 있으므로 무조건 평행사변형을 만들 수 있다. 그래서 어떻게 만드는데? 종이의 임의의 삼각형을 하나 그려보자. 그리고 점을 찍다 보면 다음과 같은 평행사변형들을 만들 수 있다. 즉 평행사변형이 .. 백준 14400 - 편의점 2 www.acmicpc.net/problem/14400 새로 세우려는 편의점과 모든 주요 고객들의 맨하탄 거리가 최소가 되는 값을 찾아야 한다. 일직선 그래프의 경우에 대해 먼저 생각해보자. 일직선 그래프에서 모든 정점들과의 거리가 최소가 되는 좌표는 가운데에 위치한 점, 좌표들의 중앙값일 것이다. 이를 평면 그래프로 확장하면 X축에서 x좌표의 중앙값과 Y축에서 y좌표의 중앙값이 맨하탄 거리의 합을 최소로 하는 좌표가 된다. 정렬을 통해 각 축의 중앙값을 찾아 좌표를 만들고 해당 좌표와 고객들 사이 맨하탄 거리를 더해주면 답이 나온다. 전체코드 - 값이 int 범위를 넘어섬에 유의하자. #include using namespace std; using ll = long long; bool cmp(pair &.. 이전 1 다음
