kotlin coding test course, calculating the area of a polygon

In today’s lecture, we will explain the problem of calculating the area of a polygon. This problem is one of the frequently asked questions in coding tests, and we will learn how to implement an algorithm to calculate the area when given various shapes of polygons.

Problem Description

Write an algorithm to calculate the area of a polygon formed by given multiple points. The points are represented as coordinates on a 2D plane, and it is assumed that the points are given in either clockwise or counterclockwise order.

Example Input

    4
    0 0
    4 0
    4 3
    0 4
    

Example Output

    14.0
    

Here, the area is determined by the coordinates of the vertices that make up the polygon. In the above example, the given points are the vertices of a polygon consisting of (0,0), (4,0), (4,3), and (0,4). In this case, the area of the polygon is 14.0.

Algorithm Explanation

There are various methods to calculate the area of a polygon, but one commonly used method is the ‘Shoelace Formula’. Using this formula, the area can be calculated with a time complexity of O(n).

Shoelace Formula

The Shoelace Formula is expressed as follows:

A = 0.5 * | ∑(xiyi+1 - xi+1yi) |

Here, x_i and y_i are the x and y coordinates of the i-th vertex of the polygon. When the polygon has n vertices, i increments from 0 to n-1. The last vertex closes back to the first vertex (i.e., when increasing i+1, it wraps around to n).

Problem Solving Process

1. Processing Input Data

First, we need to read the number of vertices and the vertex coordinates of the polygon provided as input. In Kotlin, we can use a list to store the coordinates.