백준 2987번 사과나무 (c++)

구해야 할것은 두가지이다

1. 삼각형의 넓이 구하기 <- 문제에 수식이 있으므로 그대로 구현

2. 주어진 좌표가 삼각형 내부에 있는지 판단

 

이 내용은 내가 전에 충돌 구현할때 점이 삼각형 내부로 들어왔는지 판별한 적이 있기 때문에 쉽게 풀었다.

 

pair<int, int> points[3];
int n;
vector<pair<int, int>> apple;

double area()
{
	int x1 = points[0].first;
	int y1 = points[0].second;

	int x2 = points[1].first;
	int y2 = points[1].second;

	int x3 = points[2].first;
	int y3 = points[2].second;
	//|xA(yB-yC)+xB(yC-yA)+xC(yA-yB)| / 2
	return (double)abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) * 0.5f;
}

문제에 주어진 수식을 그대로 따라 써준다.

 

int cross(pair<int, int> v1, pair<int, int> v2)
{
	return v1.first * v2.second - v2.first * v1.second;
}

bool Isin(pair<int, int> p)
{
	// 0->1 1->p
	pair<int, int> v1 = { points[1].first - points[0].first, points[1].second - points[0].second };
	pair<int, int> p1 = { p.first - points[1].first , p.second - points[1].second };
	//1->2 2->p
	pair<int, int> v2 = { points[2].first - points[1].first, points[2].second - points[1].second };
	pair<int, int> p2 = { p.first - points[2].first , p.second - points[2].second };
	//2->0 0->p
	pair<int, int> v3 = { points[0].first - points[2].first, points[0].second - points[2].second };
	pair<int, int> p3 = { p.first - points[0].first , p.second - points[0].second };

	int a1 = cross(v1, p1);
	int a2 = cross(v2, p2);
	int a3 = cross(v3, p3);
	if (((a1 >= 0) && (a2 >= 0) && (a3 >= 0)) || ((a1 <= 0) && (a2 <= 0) && (a3 <= 0))) return true;
	else return false;
}

삼각형의 세 변의 벡터를 만들어준 후(한 방향으로 일정하게) 동일한 방향으로 각각의 벡터에서 목표하는 좌표로 향하는 벡터를 만들어준다

그 두개의 벡터를 각각 외적해주면 부호로 점이 직선의 왼쪽에 있는지 오른쪽에 있는지 판별할 수 있다.

삼각형이 실제로 어떻게 생겼는지는 모르나,

세 개의 결과값이 모두 같은 부호라면 삼각형 내부에 위치해 있다는 뜻이므로 true를 반환한다.

(하나의 점이 세 변 각각의 기준으로 모두 바깥쪽에 있을 수는 없다)

 

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);
	for (int i = 0; i < 3; i++)
	{
		int a, b;
		cin >> points[i].first >> points[i].second;
	}

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		apple.push_back({ a,b });
	}
	cout << fixed;
	cout.precision(1);
	cout << area() << endl;
	int cnt = 0;
	for (auto a : apple)
	{
		if (Isin(a)) cnt++;
	}
	cout << cnt << endl;
}

 소수점 한자리수까지 출력해주는 것도 잊지 않는다.