[백준 / C언어] 2166번: 다각형의 면적 (신발끈 공식)

https://www.acmicpc.net/problem/2166

2166번: 다각형의 면적

난이도: solved.ac 골드 5

 

알고리즘 분류

---

기하학

 

구현

---

신발끈 공식을 이용하면 매우 쉽게 풀 수 있다

그럼 신발끈 공식이 뭐냐!

https://ko.wikipedia.org/wiki/%EC%8B%A0%EB%B0%9C%EB%81%88_%EA%B3%B5%EC%8B%9D

신발끈 공식 - 위키백과, 우리 모두의 백과사전

아래 그림처럼 각 꼭짓점의 좌표를 교차해서 곱하고 두 개를 서로 빼 절댓값을 씌운 뒤 2로 나누는 공식이다

좌푯값을 교차하는 모습이 신발끈의 모습과 비슷하다고 해서 붙여진 이름이라고 한다

위의 그림에서 빨간 선으로 이어진 x좌표와 y좌표를 곱한 값을 sum1, 파란 선으로 이어진 x좌표와 y좌표를 곱한 값을 sum2라고 하였다

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

int main() {
	int N, i, j;
	scanf("%d", &N);
	double* x = (double*)calloc(N, sizeof(double));
	double* y = (double*)calloc(N, sizeof(double));

	for (i = 0; i < N; i++)
		scanf("%lf %lf", &x[i], &y[i]);

	double sum1 = 0, sum2 = 0, Area;
	for (i = 0; i < N - 1; i++) {
		sum1 += x[i] * y[i + 1];
		sum2 += x[i + 1] * y[i];
	}
	sum1 += x[N - 1] * y[0];
	sum2 += x[0] * y[N - 1];
	
	Area = (sum1 - sum2) / 2;
	if (Area < 0)
		Area = -Area;

	printf("%0.1f", Area);
	free(x);
	free(y);
	return 0;
}