Tính diện tích tam giác - Phần 1

Cấu trúc dữ liệu và giải thuật

0.0 (0 đánh giá)
Tạo bởi Katsu Cập nhật lần cuối 13:56 08-07-2022 913 lượt xem 0 bình luận
Tác giả/Dịch giả: huulam3011 K9
Học nhanh

Danh sách bài học

Tính diện tích tam giác - Phần 1

Dẫn nhập

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ề:

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:

  • Gồm 3 dòng, mỗi dòng cho bởi 2 số nguyên dương (X_{i},Y_{i}) thể hiện cho toạ độ đỉnh của tam giác (0\leq X_{i}, Y_{i} \leq 10^{5})

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

Chương trình tính diện tích tam giác


Ý 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 a, b, c là độ dài ba cạnh tam giác, p là nửa chu vi. Khi đó, diện tích tam giác được tính như sau: S = \sqrt{p(p-a)(p-b)(p-c)}

Phương pháp tính của ta như sau:

Từ các đỉnh A, B, C ta lần lượt hạ các đường vuông góc xuống trục Ox tại các điểm M, N, P

Ta thấy, S_{ABC}=S_{AMNC}+S_{CNPB} - S_{BPMA}. 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 AMND, CNPB và BPMA. 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ụ: S_{AMNC}= \frac{(AM+NC) \times MN}{2}


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 S_{ABC}=S_{AMNC}+S_{CNPB} - S_{BPMA} với 2. Khi đó, 2\times S_{ABC}= (AM + NC)\times MN + (CN + BP)\times NP - (AM + BP)\times MP

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, \dpi{100} \large 2\times S_{ABC}= ((Y_{A} - Y_{M}) + (Y_{C} - Y_{N}) ) \times (X_{N} - X_{M}) + ((Y_{C} - Y_{N}) + (Y_{B} - Y_{P}))\times (X_{P} - X_{N}) - ((Y_{A} - Y_{M})+ (Y_{B} - Y_{P})) \times (X_{P} - X_{M})

Biến đổi tương đương ta được \large 2\times S_{ABC}= ((Y_{A} - Y_{M}) + (Y_{C} - Y_{N}) ) \times (X{_C} - X_{A}) + ((Y_{C} - Y_{N}) + (Y_{B} - Y_{P}))\times (X_{B} - X_{C}) + ((Y_{A} - Y_{M})+ (Y_{B} - Y_{P})) \times (X_{A} - X_{B})

Tương đương 2\times S_{ABC}= (Y_{A} + Y_{C})\times(X_{C} - X_{A}) + (Y_{C} + Y_{B}) \times (X_{B} - X_{C}) + (Y_{A} + Y_{B})\times (X_{A} - X_{B}) do (Y_{M}=Y_{N}=Y_{P}=0)

Tổng quát hơn, ta có công thức sau:

Gọi (X_{1},Y_{1}), (X_{2},Y_{2}), (X_{3},Y_{3}) 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:

S = (Y_{2} + Y_{1}) \times (X_{2} - X_{1}) + (Y_{3} + Y_{2}) \times (X_{3} - X_{2}) +(Y_{1} + Y_{3}) \times (X_{1} - X_{3})


Code

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Point{
    int x, y;

    Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
} A, B, C;

ll area(Point a, Point b, Point c){
    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);
}

int main(){
    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 << ans / 2 << ".5" << endl;
    else cout << ans / 2 << ".0" << endl;

    return 0;
}

Vấn đề kì sau

Mình có một vấn đề mở ra cho các bạn như sau:

Ở trong đoạn code trên, ta đang để thứ tự các đỉnh trong hàm là A, C, B. Điều gì xảy ra nếu như thứ tự đỉnh trong hàm đổi thành A, B, C. Các bạn hãy làm thử để nhận xét rồi thử xem liệu có tìm ra được nguyên nhân và ý nghĩa của vấn đề này không nhé.


Kết luận

Qua bài này chúng ta đã nắm về Tính diện tích tam giác

Bài sau chúng ta sẽ tiếp tục tìm hiểu về Tính diện tích tam giác với một số các tính chất thu được từ diện tích tam giác

Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.


Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.

Nội dung bài viết

Tác giả/Dịch giả

Mình là Nguyễn Hữu Lâm, một người có niềm đam mê rất lớn đối với lập trình. Hiện tại, mình đang là sinh viên Khoa học máy tính của Đại học Bách Khoa Hà Nội. Mong muốn của mình là có thể chia sẻ những kiến thức mà bản thân có cho mọi người, học hỏi, kết bạn với tất cả những người có cùng đam mê với mình.


K9

Nhà sáng lập Howkteam.com, KQuiz.vn & tác giả các khóa học C#, Auto, Unity3D, Python....

Với mong muốn mang đến kiến thức chất lượng, miễn phí cho mọi người, với tâm huyết phá bỏ rào cản kiến thức từ việc giáo dục thu phí. Tôi đã cùng đội ngũ Kteam đã lập nên trang website này để thế giới phẳng hơn.
Hãy cùng chúng tôi lan tỏa kiến thức đến cộng đồng! 

Khóa học

Cấu trúc dữ liệu và giải thuật

Bạn đã từng đau đầu với các cấu trúc stack, queue,.. hoặc cảm thấy cực kỳ khó khăn với các thuật toán sắp xếp, tìm kiếm được sử dụng trong lập trình. Đừng lo lắng! Trong khoá học này, chúng ta sẽ cùng nhau tìm hiểu một cách đơn giản nhất về cấu trúc dữ liệu và giải thuật, cũng như giúp bạn nắm rõ hơn về các kiến thức này.

Hãy cùng xem cấu trúc dữ liệu và giải thuật có gì đáng sợ không nhé!

Đánh giá

Bình luận

Để bình luận, bạn cần đăng nhập bằng tài khoản Howkteam.

Đăng nhập
Không có video.