Remember this impression? This is one of Adam's relive memories of during 2026 ICPC Teams Mini Comp.

“If all the angles in the concave polygon are acute, I should have got an AC! And we should have ranked higher than Culver and Sharky!” Adam exclaimed.

His code during contests failed in exactly one $(\gt 3)$-sided polygon case

a proof on why $(\gt 3)$-sided polygon must have at least 1 non-acute angle

by Gemini

To prove that only a triangle ($n=3$) can have all acute interior angles at a university level, we utilize the Exterior Angle Sum Theorem for convex polygons or the Interior Angle Sum Formula.

1. The Direct Proof (Using Interior Angles)

Let $P$ be a convex polygon with $n$ vertices. Let the interior angles be denoted by $\alpha_1, \alpha_2, \dots, \alpha_n$. The sum of the interior angles is given by: $$\sum_{i=1}^{n} \alpha_i = (n-2)\pi$$

If we assume the polygon is strictly acute, then every angle $\alpha_i$ must satisfy $\alpha_i \lt \frac{\pi}{2}$. Therefore, the sum of all angles must satisfy:
$$\sum_{i=1}^{n} \alpha_i \lt n\left(\frac{\pi}{2}\right)$$

For the polygon to exist, the actual sum must be less than the theoretical maximum for acute angles: $$(n-2)\pi \lt \frac{n\pi}{2}$$ Dividing both sides by $\pi$ (since $\pi > 0$): $$n - 2 \lt \frac{n}{2}$$ $$2n - 4 \lt n$$ $$n \lt 4$$

Since a polygon must have $n \ge 3$ sides, the only integer solution for $n$ is $3$.

2. The Exterior Angle Proof (Topological Perspective)

A more elegant proof involves exterior angles. For any convex polygon, the sum of the exterior angles $\theta_i$ is always $2\pi$: $$\sum_{i=1}^{n} \theta_i = 2\pi$$

An interior angle $\alpha_i$ and its corresponding exterior angle $\theta_i$ are supplementary ($\alpha_i + \theta_i = \pi$).
• If an interior angle is acute ($\alpha_i \lt \frac{\pi}{2}$), then the exterior angle must be obtuse ($\theta_i \gt \frac{\pi}{2}$).

If all $n$ interior angles are acute, then all $n$ exterior angles must be greater than $\frac{\pi}{2}$. This leads to the inequality: $$\sum_{i=1}^{n} \theta_i \gt n\left(\frac{\pi}{2}\right)$$

Substituting the known sum of exterior angles: $$2\pi > \frac{n\pi}{2}$$ $$4 > n$$

Again, we find that $n$ must be less than 4.

3. Conclusion and Geometric Interpretation

For $n=3$ (a triangle), the average interior angle is $\frac{(3-2)180^\circ}{3} = 60^\circ$. Since $60^\circ \lt 90^\circ$, acute triangles (like equilateral triangles) are possible.

For $n=4$ (a quadrilateral), the average interior angle is $\frac{(4-2)180^\circ}{4} = 90^\circ$. For all angles to be acute, their sum would be $\lt 360^\circ$, which violates the Euclidean plane geometry requirement that the sum must be exactly $360^\circ$. For any $n \ge 4$, the "angular deficit" required to keep the angles acute prevents the polygon from closing.

QED!!!




“No one likes obtuse angles! No one likes geometry in ICPC!” Adam murmured, “Let me challenge you with an acute angle trigonometry problem!”

“Firstly, these are the three trivial trigonometry ratios.”

“Secondly, let me spoil you some trivial observations for solving this problem”

This is the pythagorean identity:

sin^2(x) + cos^2(x) ≡ 1

And these are some relationships between $sin$ and $cos$

sin^2(90°-x) ≡ cos^2(x)

cos^2(90°-x) ≡ sin^2(x)

“And your trivial task is to sum all of the $N$ sin^2(x), cos^2(x), sin^2(90-x) and cos^2(90-x) I give you. Express the sum of them in terms of A + B * sin^2(x) + C * cos^2(x) where $A$, $B$ and $C$ are non-negative integers, and $A$ is maximized."

Formally, find
$$\sum_{i=1}^{N} S_i \in \{ \sin^2(x), \cos^2(x), \sin^2(90-x), \cos^2(90-x) \}$$ Express it in terms of $A + B \times \sin^2(x) + C \times \cos^2(x)$, where $A$ is maximized and $A,B,C \in \mathbb{W}$

Input

The first line contains an integer $N$, which is the number of things she wants to sum up.
The next $N$ lines each contains one of sin^2(x), cos^2(x), sin^2(90-x) and cos^2(90-x).

Output

Output in the format A + B * sin^2(x) + C * cos^2(x) where $A$, $B$ and $C$ are non-negative integers, where $A$ is maximized.

Subtasks

For all cases,
$1 \le N \le 10^5$

Subtask 1 (30 pts): $N=2$
Subtask 2 (20 pts): The input contains sin^2(x) only
Subtask 3 (30 pts): The input contains sin^2(x) and cos^2(x) only.
Subtask 4 (20 pts): No additional constraints

Sample Test Cases

Input Output
5
sin^2(x)
cos^2(90-x)
sin^2(90-x)
sin^2(x)
cos^2(x)
2 + 1 * sin^2(x) + 0 * cos^2(x)
sin^2(x) + cos^2(90-x) + sin^2(90-x) + sin^2(x) + cos^2(x)
= sin^2(x) + sin^2(x) + cos^2(x) + sin^2(x) + cos^2(x)
= sin^2(x) + (sin^2(x) + cos^2(x)) + (sin^2(x) + cos^2(x))
= sin^2(x) + 1 + 1
= 2 + 1 * sin^2(x) + 0 * cos^2(x)
2
sin^2(x)
sin^2(90-x)
1 + 0 * sin^2(x) + 0 * cos^2(x)
Click to copy.

Scoring: Per Subtask
Authored by wy24215
Appeared in WYOI Round 1 [APIO & TFT Practice]