[백준 11758] CCW (C#, C++) - soo:bak

문제 링크

11758번 - CCW

설명

세 점이 평면상에서 이루는 회전 방향을 판별하는 문제입니다.

• 평면 위의 서로 다른 세 점이 주어집니다.
  
• 이 세 점이 이루는 방향이 반시계 방향이면 1, 시계 방향이면 -1, 일직선에 놓여 있으면 0을 출력해야 합니다.
  
• 좌표 정보만으로 방향성을 판별해야 하므로, 기하학적 계산이 필요합니다.
  

핵심 개념: 왜 외적(Cross Product)을 사용하는가?

세 점이 어떤 순서로 배치되어 있는지를 판별하는 데에는 외적이 적합합니다.

• 외적은 두 벡터가 이루는 평면에서의 회전 방향을 판단할 수 있는 수단입니다.
  
• 특히 2차원 공간에서는 외적의 결과가 스칼라값으로 계산되며, 이는 세 점으로 이루어진 삼각형의 부호 있는 면적과 동일합니다.
  
• 이를 통해 다음과 같은 방향성 판단이 가능합니다:
  

\[(x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1)\]

• 결과가 > 0: 반시계 방향 (CCW)
  
• 결과가 < 0: 시계 방향
  
• 결과가 = 0: 세 점이 일직선상에 있음
  

이 방식은 면적 개념을 이용하여 회전 방향을 수치적으로 확인하는 대표적인 기법입니다.

---

접근법

• 세 점의 좌표를 입력받습니다.
  
• 첫 번째 점을 기준으로 두 개의 벡터를 만들고, 그 외적을 계산합니다.
  
• 외적의 부호에 따라 방향성을 판별하여 다음과 같이 출력합니다:
  
  • 1: 반시계 방향
  • -1: 시계 방향
  • 0: 일직선

---

Code

[ C# ]

using System;

class Program {
  static double CrossProduct((double x, double y) a, (double x, double y) b, (double x, double y) c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
  }

  static void Main() {
    var p1 = Array.ConvertAll(Console.ReadLine().Split(), double.Parse);
    var p2 = Array.ConvertAll(Console.ReadLine().Split(), double.Parse);
    var p3 = Array.ConvertAll(Console.ReadLine().Split(), double.Parse);

    var a = (p1[0], p1[1]);
    var b = (p2[0], p2[1]);
    var c = (p3[0], p3[1]);

    var cross = CrossProduct(a, b, c);

    if (cross > 0) Console.WriteLine("1");
    else if (cross < 0) Console.WriteLine("-1");
    else Console.WriteLine("0");
  }
}

[ C++ ]

#include <bits/stdc++.h>

using namespace std;
typedef pair<double, double> pdd;

double crossProduct(const pdd& p1, const pdd& p2, const pdd& p3) {
  return (p2.first - p1.first) * (p3.second - p1.second) -
         (p2.second - p1.second) * (p3.first - p1.first);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  pdd p[3];
  for (int i = 0; i < 3; i++) cin >> p[i].first >> p[i].second;
  double ret = crossProduct(p[0], p[1], p[2]);
  if (ret > 0) cout << "1\n";
  else if (ret < 0) cout << "-1\n";
  else cout << "0\n";

  return 0;
}