1. 개념
신발끈 공식은 좌표평면 상에서 꼭지점의 좌표를 알 때 다각형의 면적을 구할 수 있는 방법
각 꼭짓점의 좌표값을 교차해서 곱하는 방식이 신발끈을 묶는 모습과 유사해서 신발끈공식이라고 불리며
가우스의 면적공식이나 사선공식이라고 부르기도 함
기하학문제에서 다각형의 넓이를 구할 때 사용함
2. 예시
삼각형이 있을때 해당 삼각형의 좌표가 (2, 4), (3, -8), (1, 2)라고 한다면 아래의 행렬모양처럼 진행된다.
각 좌표를 행렬처럼 나열하고 마지막값에서 처음 값으로도 연산해줘야 하는데 깔끔한 모양을 위해
첫 좌표를 마지막에 한번 더 붙여주는게 보기 편하다.
계산방식은 x1 * y2 + x2 * y3 + x3 * y4 처럼 왼쪽위 * 오른쪽아래로 나온 값들을 sum해준다.
그 후 y1 * x2 + y2 * x3 + y3 * x4 처럼 오른쪽위 * 왼쪽아래로 나온 값들을 sum해준다.
두개의 sum 결과의 차를 2로 나눈 후 절대값을 취하면 해당 다각형의 넓이가 나온다.
위의 경우
sum1 = (2 * -8) + (3 * 2) + (1 * 4) = -6
sum2 = (3 * 4) + (1 * -8) + (2 * 2) = 8
두 sum의 차는 (-6) - 8 = -14이고 2로 나눈 후 절대값을 취하면 7이므로 삼각형의 넓이는 7이다.
3. 예시문제
https://www.acmicpc.net/problem/2166
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false); cin.tie(NULL);
int N;
cin >> N;
vector<long long> x(N + 1), y(N + 1);
for (int i = 0; i < N; i++) {
cin >> x[i] >> y[i];
}
x[N] = x[0];
y[N] = y[0];
//long long sum1 = 0, sum2 = 0;
long long diff = 0;
for (int i = 0; i < N; i++) {
//sum1 += x[i] * y[i + 1]; // 계속 더해버리면 자료형 범위를 벗어날 수 있으므로
//sum2 += x[i + 1] * y[i];
diff = diff + (x[i] * y[i + 1]) - (x[i + 1] * y[i]); // 매번 빼줌
}
cout << fixed;
cout.precision(1);
//cout << abs(sum1 - sum2) / 2.0;
cout << abs(diff) / 2.0;
return 0;
}
※ 참고 문헌
https://ko.wikipedia.org/wiki/%EC%8B%A0%EB%B0%9C%EB%81%88_%EA%B3%B5%EC%8B%9D