Công thức Heron

Nguồn: CLUE OJ Độ khó: Dễ Nhập xuất Hình học Số thực

Đề bài

Cho tam giác có độ dài ba cạnh là $a, b, c$. Hãy tính diện tích tam giác đó.

Gợi ý: theo công thức Heron, với nửa chu vi $p = \dfrac{a+b+c}{2}$ thì diện tích tam giác là

$$S = \sqrt{p(p-a)(p-b)(p-c)}.$$

Dữ liệu vào: Một dòng gồm ba số nguyên dương $a, b, c$ cách nhau bởi dấu cách. Dữ liệu bảo đảm $a, b, c$ là độ dài ba cạnh của một tam giác (tổng hai cạnh bất kỳ luôn lớn hơn cạnh còn lại).

Kết quả: In ra diện tích tam giác, làm tròn đến 2 chữ số thập phân.

Giới hạn:

• $1 \le a, b, c \le 3000$

Bài được chấm với sai số tuyệt đối không quá $10^{-2}$.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

3 4 5

Ví dụ 1 – output

6.00

Ví dụ 2 – input

2 3 4

Ví dụ 2 – output

2.90

Giải thích: Ví dụ 1: $p = 6$, $S = \sqrt{6 \cdot 3 \cdot 2 \cdot 1} = 6$, in ra 6.00.

Nguồn: phỏng theo bài "CÔNG THỨC HERON" – vinhdinhcoder.net.

Lời mở đầu

Đề đã cho sẵn công thức, nên bài này không khó ở chỗ "nghĩ ra cách", mà ở chỗ làm việc với số thực cho đúng: nửa chu vi $p$ có thể là số lẻ $,5$; tích bốn thừa số rất lớn; và phải in đúng 2 chữ số thập phân. Mình sẽ chỉ ra code bẫy hay gặp, cách làm chuẩn bằng double, và một cách "toàn số nguyên" rất gọn. Mọi code đều đã chạy thật trên bộ test.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngHeronBẫychia nguyênCách 1doubleCách 216S²Tổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, bài không chia subtask; trình chấm chỉ chấp nhận sai số tuyệt đối không quá $10^{-2}$, tức là in ra lệch đáp án tối đa $0{,}01$ – với diện tích cỡ vài triệu thì phải đúng tới chữ số thập phân thứ hai! (Mình chấm các code dưới đây bằng một script nhỏ so đúng tiêu chí $|\text{ra} - \text{đáp án}| \le 10^{-2}$.)

Test	Đặc điểm
1–4, 8	tam giác nhỏ, có cả hai ví dụ của đề và tam giác "đẹp" 13–14–15
5	tam giác đều cạnh 3000 – diện tích lớn nhất ≈ 3.897.114,32
6, 7	tam giác rất "dẹt" (một cạnh rất ngắn)
9–20	cạnh ngẫu nhiên tới 3000

• Có 10 test có chu vi $a + b + c$ lẻ (test 2–3, 6–7, 9–10, 12, 14–15, 19) – lúc đó $p$ không phải số nguyên.
• Nếu tính $p(p-a)(p-b)(p-c)$ bằng int thì có 13 test bị tràn (test 5, 9–20): tích lớn nhất cỡ $1{,}5 \cdot 10^{13}$.

Ý tưởngTính theo đúng công thức Heron

Chỉ việc làm theo 3 bước: tính nửa chu vi $p$, tính tích $p(p-a)(p-b)(p-c)$, lấy căn bậc hai. Các bước trung gian nhỏ nhưng phải giữ phần thập phân của $p$. Em nhập 3 cạnh rồi bấm Tiếp để xem từng bước (và xem nếu lỡ chia nguyên thì sai thế nào):

a = b = c =

Ví dụ nhanh:

BẫyDùng int cho $p$

C++▶ Chạy tay từng dòng codeBẫy: p chia nguyên và tích 4 số int bị tràn.

Dữ liệu vào (stdin) – sửa thoải mái2 3 4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. (a + b + c) / 2 với ba số int là chia nguyên: ví dụ 2 có chu vi $9$, đúng ra $p = 4{,}5$ nhưng code tính $p = 4$, khi đó $p - c = 0$ và diện tích ra 0.00.
2. p * (p - a) * (p - b) * (p - c) nhân 4 số int nên kết quả cũng là int – với cạnh cỡ 3000, tích lên tới $10^{13}$, tràn số. Nếu tích bị tràn thành số âm thì sqrt của số âm cho ra -nan.

Kết quả chạy thật: bản C++ đúng 3/20 test, sai ở test 2–3, 5–7, 9–20; test đúng chạy lâu nhất 0.00s – chỉ đúng 3 test có chu vi chẵn và tam giác nhỏ. Bản Python với // không bị tràn số: đúng 10/20 test, sai ở test 2–3, 6–7, 9–10, 12, 14–15, 19; test đúng chạy lâu nhất 0.01s – sai đúng 10 test có chu vi lẻ.

Cách 1Heron với double

C++▶ Chạy tay từng dòng codeCách 1: công thức Heron với double, in 2 chữ số thập phân.

Dữ liệu vào (stdin) – sửa thoải mái2 3 4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Đọc thẳng a, b, c vào double nên (a + b + c) / 2 là phép chia số thực, giữ được $,5$. (Nếu đọc vào int thì viết (a + b + c) / 2.0.)
2. double có khoảng 15–16 chữ số có nghĩa, tích lớn nhất cỡ $10^{13}$ vẫn được biểu diễn rất chính xác.
3. fixed << setprecision(2) in đúng 2 chữ số sau dấu phẩy, có làm tròn (tương đương printf("%.2f", S)). Python dùng f"{S:.2f}".

Không gian$O(1)$

Thời gian$O(1)$

Kết quả chạy thật: bản C++ đúng 20/20 test; test đúng chạy lâu nhất 0.00s. Bản Python đúng 20/20 test; test đúng chạy lâu nhất 0.02s. Full điểm.

Hai lỗi nhỏ nhưng mất nửa số điểm

Mình thử thêm hai biến thể của cách 1 và chạy thật với tiêu chí sai số tuyệt đối $10^{-2}$:

• Đổi double thành float (chỉ khoảng 7 chữ số có nghĩa): với tam giác đều cạnh 3000, máy in 3897114.25 thay vì 3897114.32 – lệch $0{,}07 > 0{,}01$. Kết quả: đúng 11/20 test, sai ở test 5, 10–11, 13, 15–19; test đúng chạy lâu nhất 0.00s.
• Quên fixed << setprecision(2), chỉ viết cout << S: C++ mặc định in 6 chữ số có nghĩa, ví dụ 489471 thay vì 489471.16, 3.89711e+06 thay vì 3897114.32. Kết quả: đúng 7/20 test, sai ở test 5, 9–20; test đúng chạy lâu nhất 0.00s – chỉ qua được các test có diện tích nhỏ.

Bài học: số thực thì luôn dùng double và in đúng số chữ số thập phân đề yêu cầu.

Cách 2Toàn số nguyên: $16S^2$

Nhân công thức Heron cho 16: vì $2p = a + b + c$, $2(p - a) = b + c - a$, …, ta có

$$16S^2 = (a+b+c)(b+c-a)(a+c-b)(a+b-c).$$

Vế phải là tích 4 số nguyên (dương, vì là tam giác), lớn nhất $9000 \cdot 3000^3 \approx 2{,}4 \cdot 10^{14}$ – vừa long long. Tính chính xác tuyệt đối, chỉ lấy căn một lần ở cuối: $S = \dfrac{\sqrt{X}}{4}$.

C++▶ Chạy tay từng dòng codeCách 2: 16S² = (a+b+c)(b+c−a)(a+c−b)(a+b−c) tính bằng long long, lấy căn một lần.

Dữ liệu vào (stdin) – sửa thoải mái2 3 4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Phải dùng long long cho a, b, c (hoặc cho X và ép kiểu trước khi nhân), nếu không tích vẫn bị tràn như ở phần bẫy.
2. sqrt((double)X): đổi sang số thực trước khi lấy căn.

Không gian$O(1)$

Thời gian$O(1)$

Kết quả chạy thật: bản C++ đúng 20/20 test; test đúng chạy lâu nhất 0.00s. Bản Python đúng 20/20 test; test đúng chạy lâu nhất 0.02s. Full điểm.

Tổng kếtKết quả chạy thật trên bộ test

Code	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Bẫy: int p, nhân int	C++	3/20	0.00s	Sai test 2–3, 5–7, 9–20
Bẫy: p = (a+b+c) // 2	Python	10/20	0.01s	Sai test 2–3, 6–7, 9–10, 12, 14–15, 19
Cách 1: Heron với double	C++	20/20	0.00s	Full điểm
	Python	20/20	0.02s	Full điểm
Cách 1 nhưng dùng float	C++	11/20	0.00s	Sai test 5, 10–11, 13, 15–19 (float thiếu chính xác)
Cách 1 nhưng quên fixed	C++	7/20	0.00s	Sai test 5, 9–20 (in 6 chữ số có nghĩa)
Cách 2: $16S^2$ số nguyên	C++	20/20	0.00s	Full điểm
	Python	20/20	0.02s	Full điểm

Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình (giới hạn 1 giây), mọi code chạy tức thì. Mọi kết quả chấm theo đúng tiêu chí của đề: sai số tuyệt đối không quá $10^{-2}$. Thói quen tốt với bài số thực: luôn dùng double, chú ý chia nguyên khi các số đều là int, và in đúng số chữ số thập phân.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇