Problem A. 雷射防護網
https://tioj.ck.tp.edu.tw/problems/1511
Description
考慮在正n邊形的頂點中任選三點形成的三角形,請統計分別有幾個銳角三角形、直角三角形和鈍角三角形
注意:兩個三角形被視為不同的,若且唯若三個頂點的編號不完全相同,並且不可以旋轉三角形
n≤106
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組正整數解,可以知道所求即是
a=⌊n/2⌋+1∑n−2n−a−1=i=1∑n−2−⌊n/2⌋i=2(n−2−⌊n/2⌋)(n−2−⌊n/2⌋+1)
記得要乘上n,代表以每個頂點當作鈍角頂點
又所有三角形的個數就是(3n)=6n(n−1)(n−2)
扣掉直角及鈍角的個數就是銳角的個數了
這裡比較慘的是雖然題目的範圍似乎不會讓答案超過 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';
}
}
|