Hướng dẫn giải của HSG THPT Thanh Hóa 2020 - Tam giác
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Gọi ~x,y,z~ lần lượt là độ dài của ba cạnh tam giác. Không mất tính tổng quát, ta giả sử ~x \le y \le z~.
Ta có các tính chất:
~x^2 + y^2 < z^2~ thì tam giác này nhọn.
~x^2 + y^2 = z^2~ thì tam giác này vuông.
~x^2 + y^2 > z^2~ thì tam giác này tù.
Dựa vào các tính chất trên, ta có thể đếm số bộ tam giác tương ứng bằng cách sắp xếp dãy ~a~ lại theo chiều không giảm. Bài toán quy về đếm số bộ ba ~(i,j,k)~ thỏa mãn ~1 \le i < j < k \le n~ và bộ ~(a_i,a_j,a_k)~ tương ứng với ~(x,y,z)~. Ta có thể dùng hai vòng ~for~ để cố định ~i~ và ~j~, sau đó đếm số ~k~ thỏa mãn. Việc này có thể làm bằng tìm kiếm nhị phân hoặc tối ưu nhất là dùng hai con trỏ.
Bình luận
Ai bt code ko cho tui code vs
bài này dùng python có thể AC không nhỉ?
Ad ơi tam giác nhọn phải là x ^ 2 + y ^ 2 > z ^ 2 còn tam giác tù là x ^ 2 + y ^ 2 < z ^ 2