안녕하세요,
재재입니다.
BOJ 2987 사과나무 문제 풀이입니다.
BOJ 2987 사과나무
(1) 문제 설명
출처 : https://www.acmicpc.net/problem/2987
삼각형의 세 점이 주어지며, 이후 N개의 점이 주어집니다.
이 각 점들이 삼각형에 포함되는 점이면, 개수를 카운트 해주면 됩니다.
(2) 풀이 도출
삼각형의 넓이를 통해서 접근이 가능합니다.
삼각형을 점을 기준으로 다시 쪼개서 넓이를 구해서 더해보면 알 수 있습니다.
다시 말해서,
$$ triangle(a,b,c) = triangle(a,b,x) + triangle(b,c,x) + triangle(c,a,x) $$ 를 만족한다면,
이 점은 삼각형의 내부의 점에 해당된다고 할 수 있습니다.
삼각형의 넓이는 일명 신발끈 정리로 쉽게 구할 수 있습니다.
(3) 정답 코드
BOJ 2987 사과나무