CF 102697004 - Polygons

CF 102697004 - Polygons

Rating: -
Tags: -
Solve time: 2m 26s
Verified: yes

Solution

Problem Understanding

The problem asks for the total measure of the interior angles of a polygon when the number of its sides is known. For every test case, the input gives a polygon side count, and the output should be the sum of all interior angles for a polygon with that many sides. The problem comes from a basic geometric observation: adding one extra side to a polygon increases the angle sum by exactly 180 degrees.

A polygon with n sides can be split into n - 2 triangles by drawing diagonals from one vertex. Since every triangle contributes 180 degrees, the total angle sum is (n - 2) * 180. The input contains multiple independent test cases, so the algorithm must apply this formula separately to each polygon.

The constraints are small, with the side count limited to 100. This means even a direct simulation would be fast enough, but the intended solution should use the mathematical relationship instead of repeatedly adding angles. The required work per test case is constant, so even a very large number of test cases would only require linear time in the number of test cases.

The main edge cases come from using the formula incorrectly. A common mistake is treating the number of sides as the number of triangles, forgetting that a polygon with n sides creates only n - 2 triangles.

For example, if the input is:

1
3

the correct output is:

180

A careless implementation that multiplies n by 180 would output 540, because it ignores that a triangle has no diagonals and consists of only one triangle.

Another case is a quadrilateral:

1
4

The correct output is:

360

The polygon is divided into two triangles, not four, so the answer comes from (4 - 2) * 180.

Approaches

The brute-force approach would be to start from a triangle with an angle sum of 180 degrees and repeatedly add 180 degrees for every additional side until reaching the desired number of sides. This approach is correct because each new side contributes exactly one more triangle to the triangulation. For a polygon with n sides, this performs n - 2 additions.

With the given bound of n <= 100, this is already fast enough. However, it repeats work that can be compressed. If we expand the additions mathematically, the sum becomes:

180 + 180 + ... + 180

with exactly n - 2 terms, which is simply (n - 2) * 180.

The observation that every polygon can be triangulated into exactly n - 2 triangles removes the need for iteration. The solution becomes a single multiplication for every test case.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n) per test case	O(1)	Accepted, but unnecessary
Optimal	O(1) per test case	O(1)	Accepted

Algorithm Walkthrough

1. Read the number of test cases. Each test case describes one polygon independently.
2. For each polygon, read the number of sides n. A polygon with n sides can be split into n - 2 triangles by drawing diagonals from one vertex. Each of those triangles contributes 180 degrees to the interior angle sum.
3. Compute (n - 2) * 180 and output the result. The multiplication directly represents the number of triangles multiplied by the contribution of each triangle.

Why it works:

The algorithm relies on a fixed geometric property: every simple polygon with n sides can be divided into exactly n - 2 triangles. Since the sum of angles inside every triangle is always 180 degrees, the polygon's total interior angle sum must be the number of triangles times 180. The formula accounts for every possible valid polygon size, so no special construction or simulation is needed.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    ans = []

    for _ in range(t):
        n = int(input())
        ans.append(str((n - 2) * 180))

    sys.stdout.write("\n".join(ans))

if __name__ == "__main__":
    solve()

The program first reads t, the number of polygons to process. It then handles each side count independently.

The expression (n - 2) * 180 is the entire mathematical solution. The subtraction must happen before multiplication because the polygon does not represent n triangles, it represents n - 2 triangles.

The output values fit easily inside normal integer ranges because the maximum side count is small. Python integers also remove any concern about overflow.

Worked Examples

For the sample input:

4
3
4
5
6

the trace is:

Step	n	Number of triangles	Formula	Output
1	3	1	(3 - 2) * 180	180
2	4	2	(4 - 2) * 180	360
3	5	3	(5 - 2) * 180	540
4	6	4	(6 - 2) * 180	720

This demonstrates that increasing the side count by one increases the answer by exactly 180 degrees.

For a custom input:

3
3
8
10

the trace is:

Step	n	Number of triangles	Formula	Output
1	3	1	(3 - 2) * 180	180
2	8	6	(8 - 2) * 180	1080
3	10	8	(10 - 2) * 180	1440

This confirms that the formula handles larger polygons without needing to build the polygon or perform repeated additions.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(T)	Each test case requires one subtraction and one multiplication
Space	O(T)	The program stores the output strings before printing

The algorithm easily satisfies the limits because it avoids any loop proportional to the number of sides. The work grows only with the number of test cases.

Test Cases

import sys
import io

def solve():
    input = sys.stdin.readline
    t = int(input())
    ans = []
    for _ in range(t):
        n = int(input())
        ans.append(str((n - 2) * 180))
    sys.stdout.write("\n".join(ans))

def run(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout

    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    solve()

    result = sys.stdout.getvalue()

    sys.stdin = old_stdin
    sys.stdout = old_stdout

    return result

assert run("""4
3
4
5
6
""") == "180\n360\n540\n720", "sample 1"

assert run("""1
3
""") == "180", "triangle"

assert run("""1
100
""") == "17640", "maximum side count"

assert run("""5
4
4
4
4
4
""") == "360\n360\n360\n360\n360", "all equal values"

assert run("""3
5
6
7
""") == "540\n720\n900", "consecutive side counts"

Test input	Expected output	What it validates
Triangle input	180	Minimum meaningful polygon case
100 sides	17640	Upper boundary handling
Repeated quadrilaterals	360 repeatedly	Independent test case processing
Consecutive side counts	540, 720, 900	Correct growth pattern

Edge Cases

For a triangle:

1
3

the algorithm computes (3 - 2) * 180, leaving exactly one triangle. The output is 180, which avoids the common mistake of multiplying the side count itself.

For a quadrilateral:

1
4

the algorithm computes (4 - 2) * 180, producing 360. A quadrilateral splits into two triangles, so the result comes from two contributions of 180 degrees.

For the largest allowed polygon:

1
100

the algorithm computes (100 - 2) * 180 = 17640. The same formula applies without extra handling, showing that the implementation does not depend on small polygon sizes.