[BOJ] 2987 사과나무

문제

백준이는 사과나무가 N개 심어져있는 땅의 일부를 구매했다. 백준이가 구매한 땅은 삼각형이다. 따라서, 어떤 사과나무가 백준이의 것인지 알기가 힘들었다.

백준이 땅의 꼭짓점 좌표와 사과나무의 좌표가 주어졌을 때, 백준이 땅의 넓이와 백준이의 사과나무의 개수를 구하는 프로그램을 작성하시오.

만약, 어떤 사과나무가 땅의 경계선에 걸쳐있다면, 이것은 백준이 사과나무이다.

(xA,yA), (xB,yB), (xC,yC) 로 이루어진 삼각형의 넓이는 다음과 같이 구할 수 있다.

|xA(yB-yC)+xB(yC-yA)+xC(yA-yB)| / 2

입력

처음 세 개의 줄은 삼각형의 꼭짓점 좌표이다. 다음 줄에는 사과나무의 개수 N이 주어진다. (1 ≤ N ≤ 100). 다음 N개의 줄에는 사과나무의 좌표가 주어진다.

모든 좌표는 1,000보다 작거나 같은 양의 정수이고, 공백으로 구분되어져 있다.

출력

첫째 줄에는 백준이 땅의 넓이를 소수점 첫째자리까지 출력하고, 둘째 줄에는 백준이의 사과나무 개수를 출력한다.

풀이

맨 처음에는 경계선에 걸쳐 있으면 백준의 사과나무라고 하길래 걸쳐 있는 나무만 백준이 나무인줄 알았다. 그러나 인터넷으로 찾아본 결과 땅 안에 있는 사과나무가 전부 다 백준이 것이고, 걸쳐 있는 것 또한 백준이꺼라는 뜻이었다. 먼저 삼각형의 넓이를 구하는 공식은 주어졌다. 구글의 도움을 얻은 결과 정말 획기적인 방법을 알게 되었다. 한 점에 대하여 만약 삼각형의 두 점과 주어진 점을 이어서 만든 삼각형 3개의 넓이의 합이 원래 삼각형과 같다면 그 점은 삼각형 내부에 있는 점이다. 반대로 같지 않다면 외부에 있는 점이다. 이 공식을 그대로 구현해서 풀었다. 좀 가독성이 떨어지게 구현해놨으니 로직만 가지고 직접 구현하는 것이 좋을 것 같다.

import sys
input = lambda: sys.stdin.readline().rstrip()
triangle  = []
Baekjoon = 0
for _ in range(3):
  triangle.append(list(map(int, input().split())))
area = abs(triangle[0][0]*(triangle[1][1]-triangle[2][1])+triangle[1][0]*(triangle[2][1]-triangle[0][1])+triangle[2][0]*(triangle[0][1]-triangle[1][1])) / 2
n = int(input())
apples =[]
for _ in range(n):
  apples.append(list(map(int, input().split())))
for a in apples:
  if abs(triangle[0][0]*(triangle[1][1]-a[1])+triangle[1][0]*(a[1]-triangle[0][1])+a[0]*(triangle[0][1]-triangle[1][1])) / 2 + abs(a[0]*(triangle[1][1]-triangle[2][1])+triangle[1][0]*(triangle[2][1]-a[1])+triangle[2][0]*(a[1]-triangle[1][1])) / 2 + abs(triangle[0][0]*(a[1]-triangle[2][1])+a[0]*(triangle[2][1]-triangle[0][1])+triangle[2][0]*(triangle[0][1]-a[1])) / 2 == area:
    Baekjoon += 1
print(area)
print(Baekjoon)

수학과 기하학은 항상 무섭다....