CSES Solutions – Polygon Lattice Points
Given a polygon, your task is to calculate the number of lattice points inside the polygon and on its boundary. A lattice point is a point whose coordinates are integers.
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: n = 4, vertices = {{1, 1}, {5, 3}, {3, 5}, {1, 4}}
Output: 6 8Input: n = 4, vertices = {{2, 4}, {3, 2}, {1, 3}, {2, 4}}
Output: 1 3
Approach:
The idea is to use calculate the area of the polygon using the shoelace formula and Pick’s theorem, which states that the number of lattice points inside a polygon is given by the following formula:
interior = (area + 2 - boundary) / 2where:
- interior is the number of lattice points inside the polygon
- area is the area of the polygon
- boundary is the number of lattice points on the boundary of the polygon
Steps-by-step approach:
- Calculates the area of the polygon using the shoelace formula.
- Calculates the number of boundary points:
- Iterates over each point in the polygon. The variable i is the index of the current point, and n is the total number of points.
- Inside the loop, the code checks the relationship between the current point (x[i], y[i]) and the next point (x[i+1], y[i+1])
- If x[i + 1] == x[i], it means that the two points are vertically aligned (i.e., they form a vertical edge). The number of boundary points on this edge is the absolute difference in their y coordinates, abs(y[i + 1] – y[i])
- If y[i + 1] == y[i], it means that the two points are horizontally aligned (i.e., they form a horizontal edge). The number of boundary points on this edge is the absolute difference in their x coordinates, abs(x[i + 1] – x[i])
- If neither of the above conditions is true, it means that the two points form a diagonal edge. The number of boundary points on this edge is the greatest common divisor (gcd) of the absolute differences in their x and y coordinates, __gcd(abs(x[i + 1] – x[i]), abs(y[i + 1] – y[i])).
- The number of boundary points calculated for each edge is added to the boundary variable.
- Uses Pick’s theorem to calculate the number of interior points.
- Prints the number of interior and boundary points.
Note: why __gcd(abs(x[i + 1] – x[i]), abs(y[i + 1] – y[i])) function is used to calculate the number of boundary points on a diagonal edge of the polygon !!
- When two points form a diagonal edge, the number of boundary points on this edge is the number of grid points that the line segment between these two points passes through.
- To calculate this, we use the greatest common divisor (gcd) of the absolute differences in their x and y coordinates. The gcd of two numbers is the largest number that divides both of them without leaving a remainder. In this context, it represents the number of grid points that the diagonal line segment intersects.
- For example, consider two points (3, 3) and (6, 6). The line segment between these points is a diagonal line that passes through (4, 4) and (5, 5). So, there are 3 boundary points on this edge: (3, 3), (4, 4), and (5, 5). The absolute differences in the x and y coordinates are 3 and 3, respectively, and their gcd is 3, which is the correct number of boundary points.
- So, the __gcd function is used to correctly calculate the number of boundary points on a diagonal edge. This ensures that the total number of boundary points on the polygon is accurate.
Below are the implementation of the above approach:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxVertices = 1e5 + 5;
int main()
{
// Number of vertices in the polygon
int n = 4;
// Arrays to store the x and y coordinates of the
// vertices Each lattice point will represented by
// {x[i], y[i]}
ll x[maxVertices] = { 1, 5, 3, 1 };
ll y[maxVertices] = { 1, 3, 5, 4 };
// Close the polygon by setting the last vertex equal to
// the first
x[n] = x[0];
y[n] = y[0];
// Variable to store the area of the polygon
ll area = 0;
// Calculate the area of the polygon using the shoelace
// formula
for (int i = 0; i < n; i++) {
area += x[i] * y[i + 1];
area -= y[i] * x[i + 1];
}
area = abs(area);
// Variable to store the number of boundary points
ll boundary = 0;
// Calculate the number of boundary points
for (int i = 0; i < n; i++) {
if (x[i + 1] == x[i])
boundary
+= abs(y[i + 1] - y[i]); // Vertical edge
else if (y[i + 1] == y[i])
boundary
+= abs(x[i + 1] - x[i]); // Horizontal edge
else
boundary += __gcd(
abs(x[i + 1] - x[i]),
abs(y[i + 1] - y[i])); // Diagonal edge
}
// Calculate the number of interior points using Pick's
// theorem
ll interior = (area + 2 - boundary) / 2;
// Print the number of interior and boundary points
cout << interior << " " << boundary << endl;
return 0;
}
import java.util.*;
import java.lang.Math;
public class Main {
// Maximum number of vertices in the polygon
static final int maxVertices = 100005;
public static void main(String[] args) {
// Number of vertices in the polygon
int n = 4;
// Arrays to store the x and y coordinates of the vertices
// Each lattice point will represented by {x[i], y[i]}
long[] x = new long[maxVertices];
long[] y = new long[maxVertices];
x[0] = 1; x[1] = 5; x[2] = 3; x[3] = 1;
y[0] = 1; y[1] = 3; y[2] = 5; y[3] = 4;
// Close the polygon by setting the last vertex equal to the first
x[n] = x[0];
y[n] = y[0];
// Variable to store the area of the polygon
long area = 0;
// Calculate the area of the polygon using the shoelace formula
for (int i = 0; i < n; i++) {
area += x[i] * y[i + 1];
area -= y[i] * x[i + 1];
}
area = Math.abs(area);
// Variable to store the number of boundary points
long boundary = 0;
// Calculate the number of boundary points
for (int i = 0; i < n; i++) {
if (x[i + 1] == x[i])
boundary += Math.abs(y[i + 1] - y[i]); // Vertical edge
else if (y[i + 1] == y[i])
boundary += Math.abs(x[i + 1] - x[i]); // Horizontal edge
else
boundary += gcd(Math.abs(x[i + 1] - x[i]), Math.abs(y[i + 1] - y[i])); // Diagonal edge
}
// Calculate the number of interior points using Pick's theorem
long interior = (area + 2 - boundary) / 2;
// Print the number of interior and boundary points
System.out.println(interior + " " + boundary);
}
// Function to calculate the greatest common divisor
static long gcd(long a, long b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
}
# Importing the gcd function from the math module
from math import gcd
# Number of vertices in the polygon
n = 4
# Arrays to store the x and y coordinates of the vertices
# Each lattice point will be represented by (x[i], y[i])
x = [1, 5, 3, 1]
y = [1, 3, 5, 4]
# Close the polygon by setting the last vertex equal to the first
x.append(x[0])
y.append(y[0])
# Variable to store the area of the polygon
area = 0
# Calculate the area of the polygon using the shoelace formula
for i in range(n):
area += x[i] * y[i + 1]
area -= y[i] * x[i + 1]
area = abs(area)
# Variable to store the number of boundary points
boundary = 0
# Calculate the number of boundary points
for i in range(n):
if x[i + 1] == x[i]:
boundary += abs(y[i + 1] - y[i]) # Vertical edge
elif y[i + 1] == y[i]:
boundary += abs(x[i + 1] - x[i]) # Horizontal edge
else:
boundary += gcd(abs(x[i + 1] - x[i]), abs(y[i + 1] - y[i])) # Diagonal edge
# Calculate the number of interior points using Pick's theorem
interior = (area + 2 - boundary) // 2
# Print the number of interior and boundary points
print(interior, boundary)
// Maximum number of vertices in the polygon
const maxVertices = 100005;
function main() {
// Number of vertices in the polygon
let n = 4;
// Arrays to store the x and y coordinates of the vertices
// Each lattice point will represented by {x[i], y[i]}
let x = new Array(maxVertices);
let y = new Array(maxVertices);
x[0] = 1; x[1] = 5; x[2] = 3; x[3] = 1;
y[0] = 1; y[1] = 3; y[2] = 5; y[3] = 4;
// Close the polygon by setting the last vertex equal to the first
x[n] = x[0];
y[n] = y[0];
// Variable to store the area of the polygon
let area = 0;
// Calculate the area of the polygon using the shoelace formula
for (let i = 0; i < n; i++) {
area += x[i] * y[i + 1];
area -= y[i] * x[i + 1];
}
area = Math.abs(area);
// Variable to store the number of boundary points
let boundary = 0;
// Calculate the number of boundary points
for (let i = 0; i < n; i++) {
if (x[i + 1] === x[i])
boundary += Math.abs(y[i + 1] - y[i]); // Vertical edge
else if (y[i + 1] === y[i])
boundary += Math.abs(x[i + 1] - x[i]); // Horizontal edge
else
boundary += gcd(Math.abs(x[i + 1] - x[i]), Math.abs(y[i + 1] - y[i])); // Diagonal edge
}
// Calculate the number of interior points using Pick's theorem
let interior = (area + 2 - boundary) / 2;
// Print the number of interior and boundary points
console.log(interior + " " + boundary);
}
// Function to calculate the greatest common divisor
function gcd(a, b) {
if (b === 0)
return a;
return gcd(b, a % b);
}
main();
Output
6 8
Time complexity: O(nlog(n)), where n is the number of vertices in the polygon, log(n) due to gcd function.
Auxiliary Space: O(n)
Contact Us