[백준] 2987 사과나무 (C++)

사과나무 문제 풀이

[백준] 2987 사과나무

문제

조건

1. 삼각형의 넓이 계산: 삼각형의 넓이는 주어진 공식을 사용하여 계산한다. \(\left| x_A(y_B - y_C) + x_B(y_C - y_A) + x_C(y_A - y_B) \right| / 2\)
2. 사과나무가 백준이의 것인지 확인: 사과나무의 좌표 (x, y)가 삼각형 내부에 있거나 경계선 위에 있으면 백준이의 사과나무로 간주한다.
3. 경계선 검사: 외적이 0일 때 해당 점이 경계선 위에 있다고 판단하고, 점이 삼각형의 경계선에 있는지 확인한다.

풀이 방식

이번 문제는 수식을 활용하는 문제였다. 여러가지 방식을 생각했고 처음에는 각 변에 외적을 계산해서 같은 부호인 경우에는 내부에 있다고 생각하는 방식으로 풀이하려고 했다. 그러나 이방식은 가장자리에 있는 사과나무를 판단하려면 좀 더 복잡한 방식을 통해 풀이해야했다. 외적을 통해 풀이하는 방식에서 첫시도에서는 등호만 포함하면 모두 고려할 수 있다고 생각했다. 그러나 외적이 0이더라도 해당 선분 내에 있는지를 판단하는 로직을 추가해야 한다는 것을 알 수 있었다.

그래서 두번째로 시도한 방식은 삼각형 내부에 있는 점을 기준으로 세변과 각각 만들어지는 삼각형의 넓이를 더했을때 이전에 구한 삼각형의 넓이와 비교해서 같은 경우가 사과나무를 소유함을 확인하는 방식으로 수정했다. 이방식은 이전에 활용한 함수를 제사용할 수 있다는 점에서 좋은 풀이 방식이라고 생각했다. 코드를 확인하려면 아래를 확인하자.

최근 들어서 수학과 기하관련 문제를 간만에 풀어보다 보니 오랜시간 생각을 해야 했다. 여러가지 방식이 있다보니 지속적으로 기하나 수학 문제를 풀어봐야겠다.

답안

참고자료

백준 사과나무 풀러가기