C++ Coding Test Course, Calculating the Area of a Polygon

In this lecture, we will explain how to calculate the area of a polygon using C++. The algorithm problem is given as follows.

Problem Description

Calculate the area of the polygon formed by the given points. The vertices of the polygon are provided in either clockwise or counterclockwise order, and the coordinates of the points are integers. The area of the polygon can be calculated using the following formula:

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

Here, (x_i, y_i) are the coordinates of the ith vertex of the polygon, and (x_n, y_n) is the last vertex of the polygon. The number of vertices of the polygon is 3 or more.

Input

• The first line contains the number of vertices N of the polygon (3 ≤ N ≤ 10⁵).
• The next N lines contain the x and y coordinates of each vertex as integers. (-10⁹ ≤ x, y ≤ 10⁹)

Output

Print the area of the polygon rounded to two decimal places.

Example Input

4
0 0
4 0
4 3
0 4

Example Output

12.00

Algorithm for Problem Solving

The algorithm for calculating the area of a polygon proceeds as follows.

1. Receive the input and store the coordinates.
2. Calculate the area of the polygon using the area formula.
3. Round the calculated area to two decimal places and output it.

1. Input Reception

First, the user must enter the number of vertices of the polygon and their coordinates. For this, we will use a vector to store the coordinates.

2. Area Calculation

To calculate the area according to the given formula, we will iterate through the given points and perform the calculations.

3. Formatting the Output

Since the output must be displayed to two decimal places, we can use C++’s iomanip header’s setprecision and fixed to format the output.

C++ Code Example

#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;  // Next point, the last point connects to the first point
        area += points[i].first * points[j].second;
        area -= points[j].first * points[i].second;
    }

    area = abs(area) / 2.0; // Take the absolute value and divide by 2.

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

    return 0;
}

Code Explanation

The above code performs the following steps to calculate the area of the polygon:

• Input Reception: First, it receives the number of vertices N and the coordinates of each vertex. To store the coordinates, vector> is used.
• Area Calculation: It calculates the area using the given area formula. The vertex indices are managed with i and j, and it implements the connection from the last point back to the first point.
• Output: It utilizes fixed and setprecision to print the calculated area to two decimal places.

Time Complexity

The time complexity of the above algorithm is O(N). This is because it visits each vertex once to calculate the area. Therefore, it executes quickly even when N is up to 10⁵.

Conclusion

Through this lecture, you learned how to efficiently calculate the area of a polygon using C++. This will greatly help in developing your algorithm problem-solving skills. Please practice with more diverse problems in the future!