Notice
Recent Posts
Recent Comments
Link
«   2024/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
Tags more
Archives
Today
Total
관리 메뉴

개발자 일기장.

백준 2166. 다각형의 면적 본문

취업/Algorithm.

백준 2166. 다각형의 면적

Azderica 2020. 3. 6. 07:10

다각형의 면적

 


Problem?

2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오.

 

Input

첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다.

 

Output

첫째 줄에 면적을 출력한다. 면적을 출력할 때에는 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 출력한다.

 

Solution

다각형을 삼각형으로 잘라서 합을 구했다.

삼각형의 넓이를 구하는 방법으로 두 벡터의 외적합을 사용하였다.

곱을 하는 경우, int의 범위를 넘길 수 있으므로 long long int형으로 문제를 해결하였다.

 

가정

pos : <int, int>형 벡터



Code

#include	<iostream>
#include	<vector>
#include	<algorithm>
using namespace std;

#define MAX 10000

int main() {
	long long int n, x, y;
	long long int ans = 0;
	vector<pair<long long int, long long int>> pos;

	cin >> n;
	for (int i = 0; i < n; i++) {
		scanf("%lld %lld", &x, &y);
		pos.push_back(make_pair(x, y));
	}

	// vector 외적
	for (int i = 1; i < n; i++) {
		ans += (pos[0].first * pos[i - 1].second + pos[i - 1].first * pos[i].second + pos[i].first * pos[0].second)
			- (pos[0].second * pos[i - 1].first + pos[i - 1].second * pos[i].first + pos[i].second * pos[0].first);
	}

	printf("%.1lf\n", abs(ans / 2.0));

	return 0;
}

 


코드 구현 및 수학 문제

'취업 > Algorithm.' 카테고리의 다른 글

백준 9252. LCS 2  (0) 2020.03.06
백준 2467. 용액  (0) 2020.03.06
백준 12852. 1로 만들기 2  (0) 2020.03.06
백준 12849. 본대 산책  (0) 2020.03.06
백준 2096. 내려가기  (0) 2020.03.03