cho n hình chữ nhật.Tính chu vi của các hình chữ nhật đó
Đây vốn là bài thi olympic lớp11,nhưng đọc lời giải ko hiểu chi cả
cho n hình chữ nhật.Tính chu vi của các hình chữ nhật đó
Đây vốn là bài thi olympic lớp11,nhưng đọc lời giải ko hiểu chi cả
Bạn cần tính chi vi ngoài và chu vi trong. Xin hỏi thêm kích thước dữ liệu của bào toán (quan trọng lắm đấy).
Phải nói rõ ràng chứ, đề cho thiếu dữ liệu.
Thi 30/4 hả?
Phải rồi. Nếu tôi đoán không lầm thì tọa độ mỗi hình chữ nhật là nguyên có giá trị tuyệt đối bé hơn 10 000. Các cạnh của hcn song song với các trục tọa độ phải không?
Đề vậy được đó, nhưng còn gì thêm không? n là số bất kì, và tìm max hả?
input
-n(số hình chữ nhật)
-n+1 dòng tiếp theo ghi tọa độ 2 đỉnh chéo nhau
output
-chu vi đa giác tìm được
Vậy mà lúc trước tui tưởng thi 30/4 môn Toán chứ.
Bài đó tui nghĩ ra cách giải này, n cỡ vài ngàn chắc chạy tốt. Nhưng với điều kiện tọa độ nguyên. Nếu ko phải sửa một ít
- Tìm tổng chu vi các hình chữ nhật
- Xét từng đoạn của mỗi cạnh của từng hình:
+ nếu nó nằm trong một hình nào đó thì trừ đi
+ nếu nó trùng một cạnh khác, thì đánh dấu đoạn đó để sau này trừ đi
+ nếu bị đánh dấu đã tính, thì trừ đi
+ nếu không, thì tiếp tục
Không biết còn trường hợp nào nữa ko?
nếu tính theo cách của bạn thì độ phức tạp của bài toán là
4*n*(4*n+n)=20*n*n
n khoảng vài ngàn chạy có vẻ ko tốt đâu!!!
độ phức tạp đa thức, và các phép tính chỉ là cộng trừ số nguyên. Không tồi đâu. Điều quan trọng là ko biết đã hết trường hợp chưa.
Các bạn phải chú ý tới kích thước của bài toán chứ. Nếu chỉ có tọa độ nguyên dương và chỉ khoảng <=10000 thì dùng mảng dấu gồm 0..10000 phần tử để làm. Nhưng theo tôi nghĩ, bạn nên tập tính diện tích trước rồi hãy tính chu vi vì nó khó lắm. Thuật toán nghiên về kỹ thuật lập trình nhiều.
Bookmarks