신발끈 공식(다각형의 넓이 구하기)

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