Cho một đường tròn với K điểm cách đều trên đường tròn. Cũng cho hai điểm A và B. Mục tiêu là đếm số tam giác có thể tạo bằng các điểm này sao cho chúng có góc tù ACB (góc lớn hơn 90°) bên trong. Các điểm A và B thỏa mãn A < B.
Ở đây K=8, A=2, B=5, số điểm = 2 (C, C') sao cho góc ACB, AC'B là góc tù.
Ví dụ
Đầu vào - k=10, A=2, B=4
Đầu ra - Số góc tù trong đường tròn với k điểm cách đều giữa 2 điểm là 1
Giải thích - Điểm sẽ là C=3
Đầu vào - k=12, A=2, B=10
Đầu ra - Số góc tù trong đường tròn với k điểm cách đều giữa 2 điểm là 3
Phương pháp sử dụng
Có thể thấy nếu cung nhỏ hơn giữa A và B thì các điểm sẽ nằm trên cung đó.
Tính cả hai cung và nếu chúng bằng nhau thì không có tam giác nào, trả về 0. Ngược lại gán count = cung nhỏ hơn (khoảng cách tính bằng số điểm).
- Nhập k, point_a, point_b nguyên
- Hàm
Obtuse_angle_circle(int point_a, int point_b, int k)trả về số góc tù - Khởi tạo count = 0
- Tính cung thứ nhất:
arc_1 = (point_b - point_a) - 1(b > a) - Tính cung thứ hai:
arc_2 = (k - point_b) + (point_a - 1) - Nếu hai cung bằng nhau trả về 0
- Nếu không bằng nhau: count = min(arc_1, arc_2)
- Trả về count
Chương trình minh họa
#include <bits/stdc++.h>
using namespace std;
int Obtuse_angle_circle(int point_a, int point_b, int k) {
int count = 0;
int arc_1 = (point_b - point_a) - 1;
int arc_2 = (k - point_b) + (point_a - 1);
if (arc_1 == arc_2)
return 0;
count = min(arc_1, arc_2);
return count;
}
int main() {
int k = 10;
int point_a = 1;
int point_b = 4;
cout << "Số góc tù trong đường tròn với k điểm cách đều giữa 2 điểm là: "
<< Obtuse_angle_circle(point_a, point_b, k);
return 0;
}
Đầu ra
Số góc tù trong đường tròn với k điểm cách đều giữa 2 điểm là: 2