BOJ 11758. CCW

🙇‍♀️[Gold V] CCW - 11758

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

분류

기하학

제출 일자

2024년 6월 9일 13:57:56

문제 설명

2차원 좌표 평면 위에 있는 점 3개 P₁, P₂, P₃가 주어진다. P₁, P₂, P₃를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 P₁의 (x₁, y₁), 둘째 줄에 P₂의 (x₂, y₂), 셋째 줄에 P₃의 (x₃, y₃)가 주어진다. (-10,000 ≤ x₁, y₁, x₂, y₂, x₃, y₃ ≤ 10,000) 모든 좌표는 정수이다. P₁, P₂, P₃의 좌표는 서로 다르다.

출력

P₁, P₂, P₃를 순서대로 이은 선분이 반시계 방향을 나타내면 1, 시계 방향이면 -1, 일직선이면 0을 출력한다.

🚀풀이

CCW (Counter Clockwise) 알고리즘은 두 점을 지나는 직선의 방향을 확인하는 알고리즘입니다.
이 알고리즘은 주로 기하학적 문제에서 사용되며, 선분과 점, 또는 세 점의 위치 관계를 판단하는 데에 활용됩니다.

주어진 세 점 A, B, C가 있을 때, CCW 알고리즘은 다음과 같은 원리를 사용하여 세 점의 위치 관계를 확인합니다:

AB 벡터와 AC 벡터의 외적을 계산합니다.
외적의 결과가 양수인 경우에는 점 A, B, C가 반시계 방향으로 순서대로 나열됩니다.
이 경우 세 점은 CCW 관계입니다.
외적의 결과가 음수인 경우에는 점 A, B, C가 시계 방향으로 나열됩니다. 이 경우 세 점은 CW 관계입니다.
외적의 결과가 0인 경우에는 세 점이 일직선 상에 위치합니다.
이러한 CCW 알고리즘은 주로 선분 교차 여부 판단, 다각형의 내부 점 판별, 볼록 다각형(Convex Hull) 구성 등 다양한 기하학적 문제에서 사용됩니다.

CCW 알고리즘은 다음과 같이 수학적으로 표현될 수 있습니다:

CCW(A,B,C)=(B.x−A.x)×(C.y−A.y)−(B.y−A.y)×(C.x−A.x)

여기서 (B.x−A.x)×(C.y−A.y) 는 AB 벡터와 AC 벡터의 외적의 z성분을 나타내며, 이 값이 양수인지 음수인지에 따라 세 점의 위치 관계를 판단합니다.

🚀코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <climits>

using namespace std;

// 점 구조체
struct Point 
{
	int x, y;
};

// 두 점을 지나는 직선의 방향을 확인하는 함수
int ccw(Point A, Point B, Point C) 
{
	int cross_product = (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);

	if (cross_product > 0) return 1;			// 반시계 방향
	else if (cross_product < 0) return -1;		// 시계 방향
	else return 0;  // 일직선
}

void solve()
{
	Point A, B, C;
	cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C.y;

	cout << ccw(A, B, C);
}

int main()
{
	FILE* stream;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen_s(&stream, "input.txt", "rt", stdin);

	solve();

	return 0;
}