Hình học trong lập trình thuật toán là một chủ đề có tính ứng dụng cao. Tuy nhiên, đây cũng là một chủ đề tương đối khó. Trong bài học nay, chúng ta sẽ cùng nhau đi tìm hiểu vấn đề đầu tiên liên quan đến hình học.
Nội dung
Để có thể tiếp thu bài học này một cách tốt nhất, các bạn nên có những kiến thức cơ bản về:
- Các kiến thức cần thiết để theo dõi khoá học
Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:
- Tính diện tích của tam giác
Bài toán đặt ra
Trên hệ tọa độ Descartes, cho một tam giác gồm 3 đỉnh xác định bởi các toạ độ . Tính diện tích tam giác đã cho.
Input:
Output:
- Một số thực duy nhất là diện tích tam giác đã cho. Kết quả làm tròn đến 1 chữ số phần thập phân.
Ví dụ:
Input Output
2 1
6 2
3 4
5 5
Giải thích ví dụ:
Đây là tam giác đã cho trên hệ toạ độ Descartes
_Howkteam_vn.png]
Ý tưởng
Ta thấy, nếu như áp dụng cách tính diện tích tam giác thông qua tính chiều cao và cạnh đáy thì sẽ vô cùng khó khăn. Một số bạn có thể đề xuất áp dụng công thức Heron. Tuy nhiên, mình sẽ giới thiệu một phương pháp tính khác, đơn giản và có ứng dụng cao hơn.
Mở rộng:
Nếu như bạn nào không biết đến công thức Heron thì nó được trình bày như sau:
Gọi là độ dài ba cạnh tam giác, là nửa chu vi. Khi đó, diện tích tam giác được tính như sau:
Phương pháp tính của ta như sau:
Từ các đỉnh ta lần lượt hạ các đường vuông góc xuống trục tại các điểm
_Howkteam_vn.png]
Ta thấy, . Do đó, bài toán bây giờ quy về thành tính diện tích các hình thang vuông và. Công việc bây giờ trở nên đơn giản hơn rất nhiều.
Nếu như bạn nào đã quên thì muốn tính diện tích hình thang vuông, ta lấy tổng chiều dài hai đáy nhân với độ dài cạnh vuông góc rồi chia cho 2.
Ví dụ:
Cách cài đặt
Để lưu trữ các điểm, các bạn có thể dùng bất cứ cấu trúc nào lưu trữ được hai phần tử. Ở đây, mình sẽ xây dựng một struct với 2 biến x, y thể hiện cho toạ độ của 1 điểm.
struct Point{
int x, y;
Point[int _x = 0, int _y = 0] : x[_x], y[_y] {}
};
Để tránh phải xử lí với số thực quá nhiều, ta sẽ nhân cả hai vế của công thức với 2. Khi đó,
Ta thấy A và M có cùng tung độ. Do đó, độ dài AM là hiệu hoành độ của A và M. Tương tự, M và N có cùng tung độ nên độ dài MN là hiệu hoành độ của M và N hay chính là hiệu hoành độ của C và A.
Do vậy,
Biến đổi tương đương ta được
Tương đương do
Tổng quát hơn, ta có công thức sau:
Gọi lần lượt là toạ độ 3 đỉnh của một tam giác. Khi đó, diện tích tam giác đó được xác định như sau:
Code
`
include
using namespace std; typedef long long ll; struct Point{
int x, y;
Point[int _x = 0, int _y = 0] : x[_x], y[_y] {}
return [a.y + b.y] * [b.x - a.x] + [c.y + b.y] * [c.x - b.x] + [a.y + c.y] * [a.x - c.x];
freopen["CTDL.inp","r",stdin];
freopen["CTDL.out","w",stdout];
cin >> A.x >> A.y;
cin >> B.x >> B.y;
cin >> C.x >> C.y;
ll ans = area[A, C, B];
if[ans % 2] cout