Counting Isosceles Acute Triangles in a Regular n‑gon – Analysis and Java Solution

The author presents a challenging algorithmic problem from an Alibaba written test: given a regular polygon with n sides (3 ≤ n ≤ 10⁷), determine how many isosceles acute‑angled triangles can be formed using only the polygon’s vertices.

Problem description : a triangle is considered different if at least one of its vertices differs; the triangle must be isosceles and have an acute vertex angle.

Analysis : The solution separates even and odd values of n because the symmetry of the polygon differs. For each vertex we count the number of possible base edges that produce an acute angle. In the even case the count of usable base lines is ⌊(n‑2)/4⌋, leading to the formula total = n * ((n-2)/4) . In the odd case the usable base lines are ⌈(n‑1)/2⌉, giving total = n * (((n-1)/2 + 1)/2) .

When n is a multiple of 3, some counted triangles are equilateral and thus duplicated three times; we subtract two‑thirds of n from the total: total -= (n/3) * 2 .

Final algorithm (Java) :

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long total;
    if (n % 2 == 0) {
        total = (long) n * ((n - 2) / 4);
    } else {
        total = (long) n * (((n - 1) / 2 + 1) / 2);
    }
    if (n % 3 == 0) {
        total -= (n / 3) * 2;
    }
    System.out.println(total);
}

The code emphasizes the need to cast to long before the multiplication to avoid 32‑bit integer overflow, and it explains common pitfalls such as integer division truncation.

In summary, the problem illustrates a typical combinatorial‑geometry challenge that can appear in technical interviews; understanding symmetry, parity, and overflow handling leads to a concise and correct solution.