문제 설명
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;
}