백준 10282 - CCW

 

 

문제 설명

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 주어진 세 개의 점이 일지선에 위치하는지, 시계방향으로 존재하는지 반시계방향으로 존재하는지 여부를 판정하는 것이다.

이를 판정하는 것을 CCW라고 한다.

이는 벡터의 외적과 관련되어 있다.

벡터의 외적의 결과는 두 벡터의 직교하는 벡터인데, 이는 좌표계에 따라 다를 수 있지만 벡터가 존재하는 방향에 따라 결과가 달라진다는 것은 같다.

즉, 세개의 점으로 두 개의 벡터를 만들고 두 벡터의 외적의 결과가 정답이 된다는 뜻이다.

외적의 결과는 벡터가 나오는 것이 맞지만, 그 벡터의 크기는 두 벡터가 이루는 평행사변형의 면적과 동일하다.

즉, 해당 면적이 음수인지 양수인지에 따라 점들이 이루는 방향을 구할 수 있다는 뜻이다.

• S = 0: 세 점이 일직선에 위치한다.
• S > 0: 세 점이 시계방향으로 위치한다.
• S < 0: 세 점이 반시계방향으로 위치한다.

 

결론적으로 주어진 세 점으로 벡터를 만들고 이를 외적 하면 된다.

이를 공식화하면 다음과 같다.

//방법1
(x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);

//방법2
(x1 * y2 + x2 * y3 + x3 * y1) - (x2 * y1 + x3 * y2 + x1 * y3);

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int CCW(vector<pair<int, int>>& points)
{
    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;


    //return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
    return (x1 * y2 + x2 * y3 + x3 * y1) - (x2 * y1 + x3 * y2 + x1 * y3);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    vector<pair<int, int>> points;

    for (int i = 0; i < 3; i++)
    {
        int a, b;
        cin >> a >> b;

        points.push_back({ a,b });
    }

    int S = CCW(points);
    if (S == 0) cout << 0;
    else if (S < 0) cout << -1;
    else cout << 1;

    return 0;
}

---