Java Coding Test Course, Calculating the Area of a Polygon

Hello! In this lecture, we will address the problem of calculating the area of a polygon. This problem will be implemented using Java, and I will explain the process of solving the problem in detail, applying basic mathematical concepts and algorithms.

Problem Description

Write a program to calculate the area of a polygon based on the coordinates of given points. The points are given in the form of (x1, y1), (x2, y2), ..., (xn, yn), and it is assumed that these points are connected to form the polygon. The area to be computed must satisfy the following conditions:

  • The points are given in a clockwise or counterclockwise direction.
  • An accurate and efficient algorithm must be implemented.

Input

The first line contains the number of points n. The following n lines contain the coordinates x, y of each point as integers.

Output

Output the area of the polygon as a real number, rounded to two decimal places.

Example Input

4
0 0
4 0
4 3
0 4

Example Output

12.00

Solution Method

There are various algorithms to calculate the area of a polygon, but in this lecture, we will use Schroder’s formula (or the polygon area formula). According to this formula, the area of a polygon A is calculated as follows:

A = 0.5 * |Σ (xiyi+1 - yixi+1)|

Here, (xi, yi) are the coordinates of each point of the polygon, and (xn+1, yn+1) = (x1, y1) to return to the first point.

Step 1: Designing the Algorithm Structure

First, let’s design the basic structure of the program. The program consists of the following four steps:

  1. Receive input
  2. Calculate area
  3. Print result
  4. Clean up

Step 2: Receiving Input

In Java, we can receive user input through the Scanner class. We will store the coordinates of each point using an ArrayList. Here is a sample code:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class PolygonArea {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // Number of points
        List points = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            points.add(new Point(x, y));
        }
        scanner.close();
    }
    
    static class Point {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

Step 3: Calculating Area

Now it is time to add a method to calculate the area. The area calculation can be done by applying the above formula for each point using a for loop:

public static double calculateArea(List points) {
    double area = 0.0;
    int n = points.size();

    for (int i = 0; i < n; i++) {
        Point p1 = points.get(i);
        Point p2 = points.get((i + 1) % n); // Next point, the last point connects to the first point
        area += p1.x * p2.y - p2.x * p1.y;
    }
    return Math.abs(area) / 2.0;
}

Step 4: Printing the Result

Finally, let’s add the code to print the calculated area in the desired format. Add the following code to the main method:

double area = calculateArea(points);
System.out.printf("%.2f\n", area);

Complete Code

Now, if we organize all the code into one, it looks like this:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class PolygonArea {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // Number of points
        List points = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            points.add(new Point(x, y));
        }
        scanner.close();
        
        double area = calculateArea(points);
        System.out.printf("%.2f\n", area);
    }

    static class Point {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static double calculateArea(List points) {
        double area = 0.0;
        int n = points.size();

        for (int i = 0; i < n; i++) {
            Point p1 = points.get(i);
            Point p2 = points.get((i + 1) % n); // Next point, the last point connects to the first point
            area += p1.x * p2.y - p2.x * p1.y;
        }
        return Math.abs(area) / 2.0;
    }
}

Conclusion

In this lecture, we solved the problem of calculating the area of a polygon. The algorithm we covered is based on Schroder’s formula, which is frequently used in actual programming competitions. Writing code at each step and implementing the algorithm ourselves must have been a very beneficial experience.

Now, you can also tackle the problem of calculating the area for various types of polygons based on this algorithm. Furthermore, I encourage you to challenge yourself to solve more advanced problems by integrating other ideas and algorithms. In the next lecture, try different algorithm problems!