BOJ 11447 - Colby’s Costly Collectibles

링크: https://www.acmicpc.net/problem/11447

문제

문제에서 정의되는 x, y, z 방향으로 1000을 넘지 않는 길이만큼 C번 움직인 후에,
마지막에 완성된 그림 속에 채워지는 삼각형의 수는 몇 개인지 맞추는 문제이다.

삼각형들은 빈 공간이 없이 빽빽하게 채워져있고, 다시 시작점으로 돌아오지 않는 잘못된 입력은 주어지지 않는다.

처음에는 x,y,z 방향을 2차원 x,y 평면으로 적당히 전사시켜서 그 넓이를 구하는 방식으로 해야하나? 라는 생각을 했다. 그 외에도 문제를 변형시키는 별 생각을 다 했는데 결국 풀이는 다각형의 면적을 구하는 문제였다.

풀이

다각형을 이루는 꼭짓점들이 주어지면, 그 다각형의 면적을 구하는 문제이다.

이건 신발끈 공식으로 해결할 수 있다. 다각형의 각 꼭짓점의 좌표를 이용해서 그 면적을 구하는 방법이다.

각 꼭짓점의 좌표를 \(x_i, y_i\)라고 하면 정의는 위와 같다. 우선 식의 정의만 보면 어려워보이지만 아래의 그림처럼 묶이기 때문에 생각보다 쉽다. 그 모양이 신발끈을 닮은 게 이름의 유래다.

문제는 각 꼭짓점들을 구하는 것인데, 문제에서는 \(x, y, z\) 방향을 아래 그림처럼 정의하고 있고

한 변의 길이를 1이라고 정했을 때, 방향 벡터 \(x\)는 \((1, 0)\)이라고 할 수 있다. 문제는 \(y\)와 \(z\)인데

정삼각형이므로 왼쪽 그림과 같이 \(y\) 방향으로 가는 벡터는 \((0.5, sin{60^\circ}\))이다. 나머지 방향들도 같은 방식으로 모두 구할 수 있다.

따라서 입력에서 x, y, z 방향이 주어질 때 마다 해당 벡터만큼 점을 이동시키면서 각 꼭짓점들을 모두 저장한다.

하지만 이렇게 구해진 꼭짓점들을 사용해서 면적을 구한다면, 한 변의 길이가 1인 삼각형으로 가정하고 구한 것이므로 보정이 필요하다.

면적을 구한 후 세 변의 크기가 1짜리인 삼각형의 크기로 나눈 이유가 그것이다.

코드

비슷한 문제

• BOJ 2166 - 다각형의 면적