C++ 코딩테스트 강좌, 다각형의 면적 구하기

이번 강좌에서는 C++을 사용하여 다각형의 면적을 구하는 방법에 대해 설명하겠습니다. 알고리즘 문제는 다음과 같이 주어집니다.

문제 설명

주어진 점들이 이루는 다각형의 면적을 구하시오. 다각형의 꼭짓점은 시계 또는 반시계 방향으로 주어지며, 점의 좌표는 정수입니다. 다각형의 면적은 다음의 공식을 통해 구할 수 있습니다:

면적 = (1/2) * | Σ (x_i * y_i+1 – x_i+1 * y_i) |

여기서 (x_i, y_i)는 다각형의 i번째 꼭짓점의 좌표이며, (x_n, y_n)는 다각형의 마지막 꼭짓점입니다. 다각형의 꼭짓점 개수는 3 이상입니다.

입력

첫 번째 줄에는 다각형의 꼭짓점 개수 N (3 ≤ N ≤ 10⁵)이 주어진다.
다음 N줄에는 각 꼭짓점의 x, y 좌표가 정수로 주어진다. (-10⁹ ≤ x, y ≤ 10⁹)

출력

다각형의 면적을 소수점 둘째 자리까지 출력한다.

예시 입력

예시 출력

12.00

문제 풀이 방법

다각형의 면적을 구하는 알고리즘은 다음과 같은 절차로 진행됩니다.

입력을 받고 좌표를 저장합니다.
면적 공식을 사용하여 다각형의 면적을 계산합니다.
계산된 면적을 소수점 둘째 자리까지 반올림하여 출력합니다.

1. 입력 받기

먼저, 사용자는 다각형의 꼭짓점 개수와 좌표를 입력해야 합니다. 이를 위해 벡터를 사용하여 좌표를 저장하겠습니다.

2. 면적 계산

주어진 공식에 따라 면적을 계산하기 위해, 주어진 점들을 반복하면서 계산을 진행합니다.

3. 출력 형식 맞추기

출력은 소수점 둘째 자리까지 표시해야 하므로, C++의 iomanip 헤더의 setprecision과 fixed를 사용하여 형식을 맞출 수 있습니다.

C++ 코드 예제

#include 
#include 
#include 

using namespace std;

int main() {
    int N;
    cin >> N;

    vector> points(N);
    for (int i = 0; i < N; i++) {
        cin >> points[i].first >> points[i].second;
    }

    double area = 0;
    for (int i = 0; i < N; i++) {
        int j = (i + 1) % N;  // 다음 점, 마지막 점은 처음 점으로
        area += points[i].first * points[j].second;
        area -= points[j].first * points[i].second;
    }

    area = abs(area) / 2.0; // 절대값을 취하고 2로 나눈다.

    cout << fixed << setprecision(2) << area << endl;

    return 0;
}

코드 설명

위의 코드는 다각형의 면적을 구하기 위해 다음의 과정을 거칩니다:

입력 받기: 먼저, 다각형의 꼭짓점 개수 N과 각 꼭짓점의 좌표를 입력받습니다. 이를 위해 vector>를 사용하여 좌표를 저장합니다.
면적 계산: 주어진 면적 공식을 사용하여 면적을 계산합니다. 이때, 꼭짓점 인덱스를 i와 j로 관리하며, 마지막 점에서 처음 점으로 다시 이어주는 형태로 구현합니다.
출력: 계산된 면적을 소수점 둘째 자리까지 출력하기 위해 fixed와 setprecision을 사용합니다.

시간 복잡도

위의 알고리즘의 시간 복잡도는 O(N)입니다. 각 꼭짓점을 한 번씩 방문하여 면적을 계산하기 때문입니다. 따라서 N이 최대 10⁵일 때도 충분히 빠르게 실행됩니다.

결론

이 강좌를 통해 C++을 사용하여 다각형의 면적을 효율적으로 계산하는 방법을 배웠습니다. 알고리즘 문제해결 능력을 기르는 데 큰 도움이 될 것입니다. 앞으로 더욱 다양한 문제를 통해 연습해보시기 바랍니다!