TIOJ-1511

2qbingxuan

2020-02-15

TIOJ , math

Problem A. 雷射防護網

https://tioj.ck.tp.edu.tw/problems/1511

Description

考慮在正$n$邊形的頂點中任選三點形成的三角形，請統計分別有幾個銳角三角形、直角三角形和鈍角三角形
注意：兩個三角形被視為不同的，若且唯若三個頂點的編號不完全相同，並且不可以旋轉三角形
$n \leq 10^6$

Solution

簡單排列組合，不過我寫好久還踩到一些坑
直角的case很容易解決，因為斜邊必須要是外接圓的直徑，故$n$得是偶數
而所有$n/2$條直徑對應的直角三角形個數就是$2(n/2-1)$

接著我們先計算鈍角的case
固定鈍角那個頂點，假設三個角的角度分別等於$a, b, c$個邊(因為是正多邊形所以可以這樣統計)，且$a > b,c$
那麼所有鈍角三角形的個數就等於$a+b+c = n$且$a > n/2$的正整數解的個數
此時枚舉$a$，$b+c=n-a$有$n-a-1$組正整數解，可以知道所求即是
$$
\sum _ {a = \left \lfloor n/2 \right \rfloor + 1} ^ {n-2} n-a-1 = \sum _ {i=1}^{n-2 - \left \lfloor n/2 \right \rfloor} i = \frac{(n-2 - \left \lfloor n/2 \right \rfloor) (n-2 - \left \lfloor n/2 \right \rfloor + 1)}{2}
$$
記得要乘上$n$，代表以每個頂點當作鈍角頂點
又所有三角形的個數就是$\binom{n}{3} = \frac{n(n-1)(n-2)}{6}$
扣掉直角及鈍角的個數就是銳角的個數了

這裡比較慘的是雖然題目的範圍似乎不會讓答案超過 long long
但計算所有三角形個數的時候可能會溢位
因此在計算銳角三角形時我先把一個$n/3$提出來，再想辦法好好約分

AC code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    ll n;
    string s, _;
    while(cin >> n >> s >> _) {
        ll h = n/2; // half
        ll right = n&1 ? 0 : n*(h-1);
        ll tmp = n-2-h;
        ll obtuse = tmp*(tmp+1)/2*n;
        // (# a + b + c = n, max(a,b,c) > n/2)
        // (sum _ {a = n/2+1}^{n-2} n-a-1) = sum _ {i=1}^{n-2-n/2} i
        // tot = n*(n-1)*(n-2)/6
        ll acute = (n-1)*(n-2)/2 - tmp*(tmp+1)/2*3;
        if(n%3 == 0)
            acute *= n/3;
        else
            acute /= 3, acute *= n;
        acute -= right;
        if(s[0] == "Right"[0])
            cout << right << '\n';
        else if(s[0] == "Acute"[0])
            cout << acute << '\n';
        else if(s[0] == "Obtuse"[0])
            cout << obtuse << '\n';
    }
}