giúp tiếp bài này với các bạn nhé
Bài 3:
Mình chưa nghĩ đc cách tốt hơn là duyệt hết. Lưu ý là bạn cần khai báo double (hoặc mình nghi là phải so sánh chuỗi) để so sánh số. Vì chiều dài tối đa của chuỗi là 150, double hoàn toàn chứa đc số này nhé.
Bài 4:
Mình ko rõ giới hạn của (xi, yi) thế nào, nhưng với N < 256 thì duyệt hết O(N^3) cỡ 2^24 vẫn chạy đc.
Mình chưa nghĩ đc cách tốt hơn là duyệt hết. Lưu ý là bạn cần khai báo double (hoặc mình nghi là phải so sánh chuỗi) để so sánh số. Vì chiều dài tối đa của chuỗi là 150, double hoàn toàn chứa đc số này nhé.
Bài 4:
Mình ko rõ giới hạn của (xi, yi) thế nào, nhưng với N < 256 thì duyệt hết O(N^3) cỡ 2^24 vẫn chạy đc.
Bạn có thể thử trường hợp 3 điểm thẳng hàng rồi tính diện tích. Mình nghĩ nó có thể bằng 0.
Code của bài 4 thì chỉ vét cạn thôi, đại khái thế này nhé.
Mã:
type arr = array[1..256] of double;
var x, y : arr;
n, i, j, k, max_i, max_j, max_k : integer;
max_area, area : double;
BEGIN
// read data
max_area := -1;
for i := 1 to n - 2 do
for j := i + 1 to n - 1 do
for k := j + 1 to n do
begin
area := abs(x[i] * (y[j] - y[k]) + x[j] * (y[k] - y[i]) + x[k] * (y[i] - y[j]));
if (max_area < area) then
begin
max_area := area;
max_i := i;
max_j := j;
max_k := k;
end;
end;
writeln(max_i, ' ', max_j, ' ', max_k);
writeln(max_area/2 :0:1);
END.- Công thức trong đề đòi hỏi phải dùng sqrt để tính độ dài. Vì sqrt rất tốn tài nguyên tính toán nên ít programmers nào thích dùng. Ngược lại, để tính diện tích tam giác, bạn có thể dùng kiến thức của lớp 10 hay 11, kết quả là 1/2 chiều dài của cross product của 2 vectors AB và AC. Cách tính khôn khéo sẽ dùng determinant của ma trận nên ko liên quan gì tới sqrt cả.
- Ko riêng gì diện tích tam giác, với đa giác có tọa độ nguyên bất kỳ thì diện tích sẽ luôn luôn là số nguyên hoặc một nửa số nguyên, ko có ngoại lệ nhé.
Thật ra, bài 4 này mình có cách giải khác rồi. Chỉ là nó cần kỹ thuật lập trính tương đối một tí. Thuật toán sẽ có độ phức tạp là O(n log n), HUGE improvement nhé bạn; n có thể tới 10^5 hay 10^6 luôn. Nếu bạn biết về bài toán convex hull (bao lồi) thì có thể nghĩ theo cách này.
- Ko riêng gì diện tích tam giác, với đa giác có tọa độ nguyên bất kỳ thì diện tích sẽ luôn luôn là số nguyên hoặc một nửa số nguyên, ko có ngoại lệ nhé.
Thật ra, bài 4 này mình có cách giải khác rồi. Chỉ là nó cần kỹ thuật lập trính tương đối một tí. Thuật toán sẽ có độ phức tạp là O(n log n), HUGE improvement nhé bạn; n có thể tới 10^5 hay 10^6 luôn. Nếu bạn biết về bài toán convex hull (bao lồi) thì có thể nghĩ theo cách này.
Cái này là bên toán rồi. Bạn tìm đọc sách là có ngay. Nó liên quan tới determinant của ma trận, cross product của 2 vectors. Xem link sau nhé:
HTML:
https://math.stackexchange.com/questions/516219/finding-out-the-area-of-a-triangle-if-the-coordinates-of-the-three-vertices-areBài viết mới nhất
-
realme ra mắt C65 5G
- Tin Tức
-
Lộ diện OPPO A3: màn hình AMOLED
- Tin Tức
