1. 길이 계산
점 $A = (a_1, a_2, \cdots , a_d)$와 점 $B = (b_1, b_2, \cdots, b_d)$ 사이의 거리는 $\sqrt{(a_1-b_1)^2 + (a_2-b_2)^2 + \cdots + (a_d-b_d)^2}$ 로 계산이 가능합니다. PS에서는 대부분 차원수가 $d=2$ 혹은 $d=3$인 상황만 고려하기 때문에 고차원에서의 점 사이의 길이 계산은 거의 필요가 없습니다 (앞으로의 내용은 2차원이라고 가정하고 설명할 예정입니다). 이를 코드로 나타내면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
struct point2 {
ll x, y;
point2() { }
point2(ll x, ll y) : x(x), y(y) { }
friend ld dist(point2 &p1, point2 &p2) {
ll dx = p1.x - p2.x, dy = p1.y - p2.y;
// return sqrt(dx*dx + dy*dy);
return hypot(dx, dy);
}
};
struct point3 {
ll x, y, z;
point3() { }
point3(ll x, ll y, ll z) : x(x), y(y), z(z) { }
friend ld dist(point3 &p1, point3 &p2) {
ll dx = p1.x - p2.x, dy = p1.y - p2.y, dz = p1.z - p2.z;
return sqrt(dx*dx + dy*dy + dz*dz);
}
};2. CCW (Counter Clock Wise)
CCW란 Counter Clock Wise의 약자로 점 $A$, $B$, $C$이 주어졌을 때, $A \rightarrow B \rightarrow C$가 반시계방향인지 시계방향인지 나타내줍니다. CCW의 공식을 소개하기에 앞서 어떻게 이 공식이 나오게 되었는지 설명해보도록 하겠습니다.
$A \rightarrow B \rightarrow C$가 반시계방향인지 시계방향인지는 위의 그림에서 $\theta$가 양수인지 음수인지로 판단할 수 있습니다. 만약, $\theta>0$면 반시계방향 (counterclockwise), $\theta=0$면 일직선 (collinear), $\theta<0$면 시계방향 (clockwise)라고 생각할 수 있습니다.
그럼 우리는 $\theta$를 구하면 됩니다. 하지만 우리의 목표가 $\theta$의 부호를 알아내는 것이라면 $\theta$ 대신 $\sin(\theta)$를 구하는 방법으로 해결할 수 있습니다. $sin(\theta)$의 식은 다음과 같습니다.
$$sin(\theta) = \frac{\overrightarrow{AB} \times \overrightarrow{AC}}{|\overrightarrow{AB}| |\overrightarrow{AC}|}$$
벡터의 길이는 양수이므로 $sin(\theta)$의 부호에 영향을 안 끼치기 때문에 $\overrightarrow{AB} \times \overrightarrow{AC}$를 계산하고 부호만 판별해주면 됩니다. 따라서, CCW의 공식은 다음과 같습니다.
$$CCW(A,B,C) = \overrightarrow{AB} \times \overrightarrow{AC} = (b_1 - a_1) \cdot (c_2 - a_2) - (c_1 - a_1) \cdot (b_2 - a_2)$$
이를 코드로 나타내면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
#define X first
#define Y second
ll ccw(pll a, pll b, pll c) {
return (b.X - a.X) * (c.Y - a.Y) - (c.X - a.X) * (b.Y - a.Y);
}3. 넓이 계산
가장 간단한 예부터 시작하겠습니다.
삼각형의 넓이를 구하는 식은 $\frac{1}{2} |\overrightarrow{AC}| \cdot |\overrightarrow{AB}| sin(\theta)$입니다. 이 공식을 변형하면 다음과 같습니다.
$$ Area(A,B,C) = \frac{1}{2} |\overrightarrow{AC}| \cdot |\overrightarrow{AB}| sin(\theta) = \frac{1}{2} |\overrightarrow{AC} \times \overrightarrow{AB}| = \frac{1}{2} |CCW(A,B,C)| $$
여기서 우리는 위에서 배운 CCW 공식을 삼각형의 넓이를 계산할 때 쓸 수 있다는 것을 알 수 있습니다. 그럼 이제 삼각형이 아닌 다각형의 넒이를 구해봅시다.
먼저 볼록다각형일 때의 경우를 살펴봅시다.
볼록$n$각형의 경우, $n-2$개의 삼각형으로 쪼갤 수 있기 때문에 불록다각형의 넓이는 삼각형의 넓이의 합으로 계산할 수 있습니다. 즉, 볼록다각형의 꼭짓점이 $P_1, P_2, \cdots, P_n$이라면, 볼록다각형의 넓이는 다음과 같습니다.
$$\begin{split}&Area(P_1, P_2, P_3) + Area(P_1, P_3, P_4) + \cdots + Area(P_1, P_{n-1}, P_n) \\ = & \frac{1}{2} \Big( |CCW(P_1, P_2, P_3)| + |CCW(P_1, P_3, P_4)| + \cdots + |CCW(P_1, P_{n-1}, P_n)|\Big)\end{split}$$
하지만, 오목다각형의 경우는 어떨까요?
오목다각형은 단순히 삼각형의 넓이의 합으로 계산하면 안 됩니다. 위의 예시에서 나오는 오목다각형의 넓이는 $Area(P_1, P_2, P_3) + Area(P_1, P_3, P_4)$가 아닌 $Area(P_1, P_2, P_3) - Area(P_1, P_3, P_4)$이기 때문입니다. 그럼 과연 언제 더하고, 언제 빼야할까요? $P_1 \rightarrow P_2 \rightarrow P_3$는 시계방향이고, $P_1 \rightarrow P_3 \rightarrow P_4$는 반시계방향인 것을 알 수 있습니다. 즉, 방향에 따라 더해주고 빼주면 되는 것입니다. 삼각형의 넓이를 구할때 저희는 $\frac{1}{2} |CCW(A,B,C)|$를 썼었습니다. 대신, 저희는 방향까지 고려하여 절댓값 부호를 빼 $\frac{1}{2} CCW(A,B,C)$로 나타낼 것입니다. 따라서, 오목다각형의 넓이는 다음과 같습니다 (볼록다각형 역시 아래 공식을 성립합니다.)
$$\frac{1}{2} |CCW(P_1, P_2, P_3) + CCW(P_1, P_3, P_4) + \cdots + CCW(P_1, P_{n-1}, P_n)|$$
(위의 식에서 절댓값이 밖으로 빠진 이유는 $P_1, P_2, \cdots, P_n$가 반시계방향으로 주어졌는지 시계방향으로 주어졌는지에 따라 부호가 반대로 되기 때문입니다.)
이를 코드로 나타내면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
#define X first
#define Y second
ll ccw(pll a, pll b, pll c) {
return (b.X - a.X) * (c.Y - a.Y) - (c.X - a.X) * (b.Y - a.Y);
}
int n;
pll points[100005];
ld area() {
ll cur = 0;
for(int i=2; i<=n-1; i++) cur += ccw(points[1], points[i], points[i+1]);
return (ld) abs(cur) / 2;
}
4. 선분 교차
선분1을 $L_1 = \bar{P_1P_2}$라 하고, 선분2를 $L_2 = \bar{P_3P_4}$라 합시다. 두 선분이 교차하는지 안 하는지 판별하는 가장 직관적인 방법은 $L_1$의 두 끝점 $P_1$과 $P_2$가 $L_2$에 대해서 서로 반댓위치에 있고, $L_2$의 두 끝점 $P_3$와 $P_4$ 역시 $L_1$에 대해서 서로 반댓위치에 있어야 한다는 것입니다. 즉, 선분이 교차하는 조건을 식으로 표현하면 아래와 같습니다.
$$\begin{split} \text{(1) } & CCW(P_1,P_2,P_3) \geq 0 \text{ and } CCW(P_1,P_2,P_4) \leq 0 \text{ or } \\ & CCW(P_1,P_2,P_3) \leq 0 \text{ and } CCW(P_1,P_2,P_4) \geq 0 \\ \text{(2) } & CCW(P_3,P_4,P_1) \geq 0 \text{ and } CCW(P_3,P_4,P_2) \leq 0 \text{ or } \\ & CCW(P_3,P_4,P_1) \leq 0 \text{ and } CCW(P_3,P_4,P_2) \geq 0\end{split}$$
위의 식에서 부등호에 등호가 있는데 그 이유는 예를 들어 $L_1$의 한 점이 $L_2$위에 있을 수도 있기 때문입니다. 하지만 위의 식에는 반례가 존재합니다. 바로 위의 그림의 세 번째 예시처럼 $L_1$과 $L_2$가 한 직선 위에 존재하지만 교차하지 않을 경우입니다. 왜냐하면 CCW의 값이 모두 0이기 때문에 위의 식을 만족하기 때문입니다.
따라서, 교차 판정을 할 때는 두 선분이 한 직선 위에 존재하는 경우를 먼저 확인해주고, 나머지 경우에는 위의 식을 통해 선분 교차 판정을 진행하면 됩니다.
이를 코드로 표현하면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define X first
#define Y second
ll ccw(pll a, pll b, pll c) {
return (b.X - a.X) * (c.Y - a.Y) - (c.X - a.X) * (b.Y - a.Y);
}
bool line_intersect(pll p1, pll p2, pll p3, pll p4) {
if(p1 > p2) swap(p1, p2);
if(p3 > p4) swap(p3, p4);
ll c1 = ccw(p1, p2, p3), c2 = ccw(p1, p2, p4), c3 = ccw(p3, p4, p1), c4 = ccw(p3, p4, p2);
if(c1 == 0 && c2 == 0 && c3 == 0 && c4 == 0) {
if(p2 < p3 || p1 > p4) return false;
return true;
}
bool flag1 = c1 <= 0 && c2 >= 0 || c1 >= 0 && c2 <= 0;
bool flag2 = c3 <= 0 && c4 >= 0 || c3 >= 0 && c4 <= 0;
return flag1 && flag2;
}