[백준 / C언어] 11758번: CCW

https://www.acmicpc.net/problem/11758

11758번: CCW

 

난이도: solved.ac 골드 5

 

 

알고리즘 분류

---

기하학

 

접근 방법

---

벡터의 외적 + 신발끈 공식을 사용한다

 

세 개의 점 P1, P2, P3가 있다고 할 때, P1에서 P2로 가는 벡터를 a, P1에서 P3로 가는 벡터를 b라고 하자

 

이때 a와 b 사이의 각도를 세타(θ)라고 하자

 

그리고 벡터 a와 벡터 b의 외적의 크기를 구한다

 

외적의 크기 공식은 다음과 같다

 

그리고 여기서 외적의 크기를 구할 때는 신발끈 공식을 활용한다

 

신발끈 공식은 아래의 포스팅을 참고하자

https://jangkunstory.tistory.com/74

[백준 / C언어] 2166번: 다각형의 면적 (신발끈 공식)

 

벡터의 외적 크기를 구한 결과가 양수면 P1, P2, P3는 반시계 방향이고, 음수면 시계 방향이다

 

이유는 다음과 같다

 

반시계 방향일 때는 세타의 범위가 0 < θ < π 이고, 시계 방향일 때는 -π < θ < 0 인데,

 

전자의 경우 sinθ는 양수가 나오고, 후자의 경우는 sinθ가 음수이기 때문이다

 

정리

---

정리하자면, 이 문제를 푸는 과정은 다음과 같다.

 

1. 점 P1, P2, P3을 바탕으로 벡터 a와 b를 만든다

 

2. 벡터 a와 b의 외적의 크기를 신발끈 공식을 이용해 구한다

 

3. 그 크기가 양수면 반시계방향, 음수면 시계방향, 0이면 일직선을 의미한다

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int main() {
	int i, sum1 = 0, sum2 = 0;
	int point[3][2];
	for (i = 0; i < 3; i++)
		scanf("%d %d", &point[i][0], &point[i][1]);
	
	for (i = 0; i < 3; i++) {
		sum1 += point[i][0] * point[(i + 1) % 3][1];
		sum2 += point[i][1] * point[(i + 1) % 3][0];
	}
	
	if (sum1 - sum2 > 0)
		printf("1");
	else if (sum1 - sum2 < 0)
		printf("-1");
	else
		printf("0");
	return 0;
}