#P1945. Counting Lattice Squares and Equilateral Triangles in a Grid
Counting Lattice Squares and Equilateral Triangles in a Grid
Counting Lattice Squares and Equilateral Triangles in a Grid
Given a grid with R rows and C columns of square cells, its intersection points are called lattice points. A lattice square is defined as a square whose four vertices are lattice points and aligned with the grid (i.e. its sides are parallel to the grid lines). Similarly, a lattice equilateral triangle is defined as an equilateral triangle with all three vertices among the lattice points.
You are given two positive integers \(R\) and \(C\) (with \(R, C \le 10\)). The grid has \(R\) rows and \(C\) columns of cells, hence \((R+1)\times(C+1)\) lattice points. Your task is to count:
- the number of lattice squares (which in this problem are only the axis‐aligned ones, i.e. with sides parallel to the grid lines), and
- the number of lattice equilateral triangles.
The answer should be output as two integers separated by a space: the first is the number of lattice squares and the second is the number of lattice equilateral triangles.
Note: For a grid with R rows and C columns, the number of axis‐aligned squares can be computed by the formula \[ S = \sum_{k=1}^{\min(R,C)} (R - k + 1)(C - k + 1). \]
inputFormat
The input consists of a single line containing two space-separated positive integers \(R\) and \(C\) (\(R, C \leq 10\)).
outputFormat
Output two integers separated by a space: the number of lattice squares and the number of lattice equilateral triangles respectively.
sample
1 1
1 0