외적 (크로스 프로덕트)
2차원에서의 정의:
[\vec{v_1} \times \vec{v_2} = x_1y_2 - y_1x_2 = -(\vec{v_2} \times \vec{v_1})]#### 특징:
- \(\vec{v_2}\)가 \(\vec{v_1}\)의 반시계 방향에 있을 때, 결과값은 양수입니다.
- \(\vec{v_2}\)가 \(\vec{v_1}\)의 시계 방향에 있을 때, 결과값은 음수입니다.
- 두 벡터가 일직선 상에 있을 경우, 결과값은 0이 됩니다.
활용 사례
- 외적 값은 두 벡터로 구성된 평행사변형의 부호를 가진 면적을 나타냅니다. 삼각형의 면적은 이 값의 절반입니다.
- 다각형의 각 변이 왼쪽으로 꺾이는지 또는 오른쪽으로 꺾이는지를 판별할 수 있습니다.
- 두 선분 AB와 CD가 교차하는지 여부를 판단:
- \((\vec{AB} \times \vec{AC}) (\vec{AB} \times \vec{AD}) < 0\) (점 C와 D가 선분 AB의 양 측에 위치) 그리고 \((\vec{CD} \times \vec{CA}) (\vec{CD} \times \vec{CB}) < 0\) (점 A와 B가 선분 CD의 양 측에 위치)
- \(\vec{AB} \times \vec{AC} = 0\) (한 끝점이 다른 선분 위에 있음) 그리고 \(min(x_A,x_B) \leq x_C \leq max(x_A,x_B) \land min(y_A,y_B) \leq y_C \leq max(y_A,y_B)\) (해당 끝점이 다른 선분 위에 있음)
- 다각형의 면적: 원점을 기준점으로 하여 각 꼭짓점과의 연결선으로 나누어진 삼각형들의 면적 합을 구합니다.
다각형의 무게 중심 찾기
무게 중심의 정의: 물리학적인 관점에서의 무게 중심
삼각형의 무게 중심 공식:
[x_g=\frac{x_1+x_2+x_3}{3}, y_g=\frac{y_1+y_2+y_3}{3}]이 공식은 모든 질량이 꼭짓점에 집중되어 있을 때만 다각형에 적용됩니다.
질량이 균일하게 분포된 다각형의 무게 중심을 구하는 방법: 임의의 한 점에서 각 꼭짓점까지의 선분으로 이루어진 삼각형들의 무게 중심 위치와 크기를 계산하여 그 값을 사용하여 가중치를 적용한 식으로 최종 무게 중심을 결정합니다.
컨벡스 헐(Convex Hull)
모든 점을 포함하는 가장 작은 볼록 다각형입니다.
특징: 컨벡스 헐의 모든 점들은 원래의 점 집합에 속해야 합니다.
그래함 스캔 알고리즘(Graham Scan)
y값이 가장 작은 점 \(p_0\)을 기준점으로 선택하고, \(\vec{p_0p_i}\)의 기울기에 따라 정렬합니다 (외적을 이용한 비교 함수로 정밀도 문제를 해결). 스택을 사용하여 컨벡스 헐의 점들을 저장하며, 각 점을 순서대로 확인하면서 현재 점과 스택의 마지막 두 점 사이의 회전 방향이 시계 방향인지 확인하여 필요하다면 스택의 마지막 점을 제거하고 현재 점을 추가합니다.
시간 복잡도는 \(O(n \log n)\).
재비스 행진법(Jarvis March)
기준점이 결정된 후, 다음 단계에서는 항상 왼쪽으로 회전하는 점을 찾아 컨벡스 헐을 업데이트합니다.
시간 복잡도는 \(O(nh)\), 여기서 h는 컨벡스 헐의 점의 개수입니다 (최악의 경우 n).
회전 카라클(Rotating Calipers)
목적: 컨벡스 헐의 지름을 구하거나 모든 점을 포함하는 최소 넓이의 직사각형을 찾습니다.
핵심 아이디어: 컨벡스 헐의 경계를 따라 반시계 방향으로 이동하며 각 변에 대해 가장 먼 점을 찾습니다. 이렇게 함으로써 전체 복잡도가 O(n)이 됩니다.
연습 문제
gxx's Problem
두 선분이 교차하는지 여부를 판단하고, 교차점이 존재한다면 출력합니다. 만약 정수가 아니라면 가장 간단한 분수 형태로 출력합니다.
두 선분의 교차점을 찾는 알고리즘은 등고선 삼각형 면적 비율과 유사 삼각형 원리를 사용합니다. 자세한 내용은 본문 참조.
#include<iostream>
#include<algorithm>
using namespace std;
long long cross(int x1, int y1, int x2, int y2){
return (long long)x1*y2 - (long long)y1*x2;
}
bool isIntersect(int xa, int ya, int xb, int yb, int xc, int yc, int xd, int yd){
long long d1 = cross(xa-xc, ya-yc, xb-xc, yb-yc);
long long d2 = cross(xa-xd, ya-yd, xb-xd, yb-yd);
long long d3 = cross(xc-xa, yc-ya, xd-xa, yd-ya);
long long d4 = cross(xc-xb, yc-yb, xd-xb, yd-yb);
if(d1*d2 < 0 && d3*d4 < 0) return true;
return false;
}
int main(){
int xa, ya, xb, yb, xc, yc, xd, yd;
cin >> xa >> ya >> xb >> yb >> xc >> yc >> xd >> yd;
if(isIntersect(xa, ya, xb, yb, xc, yc, xd, yd)) cout << "교차" << endl;
else cout << "비교차" << endl;
}
Surround the Trees
컨벡스 헐을 구하는 기본 문제입니다.
#include<iostream>
#include<algorithm>
using namespace std;
struct Point{
int x, y;
Point operator -(const Point &b) const {
return {x-b.x, y-b.y};
}
};
bool cmp(const Point &a, const Point &b){
return a.y < b.y || (a.y == b.y && a.x < b.x);
}
long long cross(Point a, Point b){
return (long long)a.x*b.y - (long long)b.x*a.y;
}
double distance(Point a, Point b){
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
int main(){
int n;
cin >> n;
Point points[n];
for(int i=0; i<n; ++i) cin >> points[i].x >> points[i].y;
sort(points, points+n, cmp);
// Convex hull construction code here...
return 0;
}
최대 삼각형
컨벡스 헐을 이용한 회전 카라클 문제입니다.
#include<iostream>
#include<algorithm>
using namespace std;
struct Point{
int x, y;
Point operator -(const Point &b) const {
return {x-b.x, y-b.y};
}
};
bool cmpY(const Point &a, const Point &b){
return a.y < b.y || (a.y == b.y && a.x < b.x);
}
long long cross(Point a, Point b){
return (long long)a.x*b.y - (long long)b.x*a.y;
}
double area(Point a, Point b){
return abs(cross(a, b)) / 2.0;
}
int main(){
int n;
cin >> n;
Point points[n];
for(int i=0; i<n; ++i) cin >> points[i].x >> points[i].y;
sort(points, points+n, cmpY);
// Maximum triangle area calculation code here...
return 0;
}