백준 2166 다각형의 면적 C++

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

CCW를 활용하여 면적을 구하는 문제이다.

여러개의 좌표가 주어질 때, CCW를 활용해서 면적을 구하는 방법에도 여러가지가 있다.

필자가 구현한 것처럼, 다각형을 이루는 점 하나를 중심으로 CCW를 돌리는 방법이 있고,

원점과 같은 다각형 외부의 정점을 잡아서 CCW를 수행하는 방법이 있다.

CCW 함수가 시행되는 횟수의 차이가 있을 것이다.

이 문제에서 또 유의할 것은, 어떤 자료형을 사용할 것이냐이다. n이 10만을 넘어가기 때문에, 면적을 구하는 과정에서 int 범위 밖으로 나갈 수 있다.

따라서 long long을 사용해주면 되겠다.

면적을 구하는 중간에 음수가 나오더라도, 계산 중간중간에 나오는 양수들 때문에 알아서 절댓값은 넓이만큼 구해지게 된다. 따라서 결과에서만 절댓값을 취하고, 2로 나눠주면 되겠다.

//좌표값 정수
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
struct POT {
    ll x, y;
}p[10001];
int n;
 
ll ccw(POT p1, POT p2, POT p3) {
    ll ret;
    ret = (p1.x*p2.y + p2.x*p3.y + p3.x* p1.y) - 
        (p1.y*p2.x + p2.y*p3.x + p3.y* p1.x);
    return ret;
}
 
int main(void) {
    cin >> n;
    for(int i = 0 ; i < n ; i++)
        cin >> p[i].x >> p[i].y;
    ll Sum = 0;
    for (int i = 0; i < n-1; i++)
        Sum += ccw(p[0], p[i], p[i + 1]);
    printf("%.1lf", abs(Sum / 2.0));
    return 0;
}

기준벡터를 원점으로 평행이동 시켜서

//좌표값 정수
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
struct POT {
    ll x, y;
    POT operator - (POT a) { return{x-a.x, y-a.y}; }
}p[10001];
 
int n;
ll ccw(POT p1, POT p2) {
    return p1.x*p2.y - p1.y*p2.x;
}
ll ccw(POT p1, POT p2, POT p3) {
    return ccw(p2 - p1, p3 - p1);
}
 
int main(void) {
    cin >> n;
    for(int i = 0 ; i < n ; i++)
        cin >> p[i].x >> p[i].y;
    ll Sum = 0;
    for (int i = 0; i < n-1; i++)
        Sum += ccw(p[0], p[i], p[i + 1]);
    printf("%.1lf", abs(Sum / 2.0));
    return 0;
}