백준 2166 - 다각형의 면적(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2166

2166번: 다각형의 면적

CCW를 이용하는 문제입니다.

CCW라는 기하 알고리즘을 사용하는 문제입니다.

https://degurii.tistory.com/47 에 잘 나와있으니 참고해주시면 감사하겠습니다.

[알고리즘] CCW로 세 점의 방향성 판별하기

 

즉, 3개의 좌표 (x1, y1) (x2, y2) (x3, y3)가 있을 때, (x1 * y2 + x2 * y3 + x3*y1) - (x2*y1 + x3*y2 + x1*y3)를 하면 3개의 좌표로 이루어진 평행사변형의 넓이를 구할 수 있습니다. 

원하는 것은 삼각형의 넓이기이에, 2를 나눠주면 됩니다.

 

그렇다면, 들어간 부분의 넓이는 어떻게 계산하는지가 문제입니다.

CCW를 통해 외적을 구하는데, 이때 방향에 따라서 부호가 바뀝니다. 들어간 부분과 나온 부분은 부호가 다르기 때문에, 두 값은 더해지지 않습니다.

하지만, 어느 좌표에서 시작하냐에 따라서 전체 값이 음수가 될 수 있습니다. 따라서, 마지막에 절댓값을 취해줘야합니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#include <map>
#define pp pair<double, double>
#define F first
#define S second

using namespace std;

int N;
vector<pp> shape;

double get_shape(pp x, pp y, pp z){
    double ans = 0;
    ans += (x.F*y.S + y.F*z.S + z.F*x.S);
    ans -= (y.F*x.S + z.F*y.S + x.F*z.S);
    return ans/2;
}

void solve(){
    double ans = 0;
    for(int i = 1; i < shape.size(); i++){
        ans += get_shape(shape[0], shape[i-1], shape[i]);
    }
    printf("%.1lf", abs(ans));
}

int main() {
    cin.tie(0);
	cout.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++){
        double x, y;
        cin >> x >> y;
        shape.push_back({x, y});
    }
    solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요