CSES Solution – Polygon Area
Your task is to calculate the area of a given polygon.
The polygon consists of n vertices (x1,y1),(x2,y2),…..(xn,yn). The vertices (xi,yi) and (xi+1,yi+1) are adjacent for i=1,2,….,n-1, and the vertices (x1,y1) and (xn,yn) are also adjacent.
Example:
Input: vertices[] = {{1, 1}, {4, 2}, {3, 5}, {1, 4}}
Output: 16Input: vertices[] = {{1, 3}, {5, 6}, {2, 5}, {1, 4}}
Output: 6
Approach:
The idea is to use Shoelace formula calculates the area of a polygon as half of the absolute difference between the sum of products of x-coordinates and y-coordinates of consecutive vertices.
Shoelace formula Formula: [Tex]A = \frac{1}{2} \left| \sum_{i=1}^{n-1} (x_i y_{i+1} – x_{i+1} y_i) + x_n y_1 – x_1 y_n \right| [/Tex]
- The formula involves summing the products of the x-coordinates of adjacent vertices and the y-coordinates of the next adjacent vertices, and then subtracting the products of the y-coordinates of adjacent vertices and the x-coordinates of the next adjacent vertices.
- The result is multiplied by 0.5 to get the area of the polygon.
Steps-by-step approach:
- Calculate the area using the shoelace formula:
- Initialize a variable area to 0.
- Iterate over the vertices of the polygon.
- For each vertex i, calculate the product of the x-coordinate of vertex i and the y-coordinate of vertex i+1, and subtract the product of the y-coordinate of vertex i and the x-coordinate of vertex i+1.
- Add the result to the area variable.
- Take the absolute value of the area:
- The shoelace formula can result in a negative area if the polygon is oriented clockwise.
- To ensure that the area is always positive, take the absolute value of the area variable.
- Return the absolute value of the area variable.
Below is the implementation of the above approach:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
int main()
{
// Number of vertices in the polygon
ll n = 4;
// Array to store the vertices of the polygon
pair<ll, ll> vertices[n]
= { { 1, 3 }, { 5, 6 }, { 2, 5 }, { 1, 4 } };
// Variable to store the area of the polygon
ll area = 0;
// Calculating the area of the polygon using the
// shoelace formula
for (ll i = 0; i < n; i++) {
area += (vertices[i].first
* vertices[(i + 1) % n].second
- vertices[(i + 1) % n].first
* vertices[i].second);
}
// Printing the absolute value of the area
cout << abs(area);
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
// Number of vertices in the polygon
int n = 4;
// Array to store the vertices of the polygon
int[][] vertices = { { 1, 3 }, { 5, 6 }, { 2, 5 }, { 1, 4 } };
// Variable to store the area of the polygon
int area = 0;
// Calculating the area of the polygon using the shoelace formula
for (int i = 0; i < n; i++) {
area += (vertices[i][0] * vertices[(i + 1) % n][1]
- vertices[(i + 1) % n][0] * vertices[i][1]);
}
// Printing the absolute value of the area
System.out.println(Math.abs(area));
}
}
# Importing the math module for absolute function
import math
# Number of vertices in the polygon
n = 4
# List to store the vertices of the polygon
vertices = [(1, 3), (5, 6), (2, 5), (1, 4)]
# Variable to store the area of the polygon
area = 0
# Calculating the area of the polygon using the shoelace formula
for i in range(n):
area += (vertices[i][0] * vertices[(i + 1) % n][1] - vertices[(i + 1) % n][0] * vertices[i][1])
# Printing the absolute value of the area
print(math.fabs(area))
using System;
public class MainClass {
public static void Main(string[] args) {
// Number of vertices in the polygon
int n = 4;
// Array to store the vertices of the polygon
Tuple<int, int>[] vertices = new Tuple<int, int>[] {
Tuple.Create(1, 3),
Tuple.Create(5, 6),
Tuple.Create(2, 5),
Tuple.Create(1, 4)
};
// Variable to store the area of the polygon
long area = 0;
// Calculating the area of the polygon using the shoelace formula
for (int i = 0; i < n; i++) {
area += (vertices[i].Item1 * vertices[(i + 1) % n].Item2)
- (vertices[(i + 1) % n].Item1 * vertices[i].Item2);
}
// Printing the absolute value of the area
Console.WriteLine(Math.Abs(area));
}
}
// Number of vertices in the polygon
let n = 4;
// Array to store the vertices of the polygon
let vertices = [ { x: 1, y: 3 }, { x: 5, y: 6 }, { x: 2, y: 5 }, { x: 1, y: 4 } ];
// Variable to store the area of the polygon
let area = 0;
// Calculating the area of the polygon using the
// shoelace formula
for (let i = 0; i < n; i++) {
area += (vertices[i].x * vertices[(i + 1) % n].y - vertices[(i + 1) % n].x * vertices[i].y);
}
// Printing the absolute value of the area
console.log(Math.abs(area));
Output
6
Time complexity: O(N^3), where N is the number of points.
Auxiliary Space: O(1)
Contact Us