Một vài bài toán về sắp xếp

algorithm

35

kiennt viết ngày 11/10/2016

Hôm nay ngồi làm bài Đếm số cặp hình tròn giao nhau, tự nhiên nghĩ ra khá nhiều bài toán con về sắp xếp.

Giờ list ra đây để giải dần

1. Đếm số đoạn thẳng giao nhau
   Cho N đoạn thẳng nằm trên trục Ox. Mỗi đoạn thẳng được mô tả bới 2 điểm [ai, bi]
   Hai đoạn thẳng được gọi là giao nhau nếu chúng có ít nhất một điểm chung.
   Tìm số cặp đoạn thẳng giao nhau với N điểm cho trước

2. Đếm số đoạn thẳng lồng nhau
   Cho N đoạn thẳng nằm trên trục Ox.
   Đoạn thẳng i được gọi là chưa trong j nếu aj <= ai <= bi <= bj
   Đếm số đoạn thẳng không bị chứa trong bất cứ đoạn thẳng nào

3. Đếm số chuỗi đoạn thẳng lồng nhau
   Giống bài 2, nhưng với yêu cầu là tất cả các đoạn thẳng trong chuỗi đều phải lồng nhau

4. Đếm số hình chữ nhật giao nhau
   Cho N hình chữ nhật trên mặt phẳng. Đếm số cặp hình chữ nhật giao nhau

5. Đếm sô hình chữ nhật lồng nhau

6. Đếm chuỗi hình chữ nhật lồng nhau

7. Cho N hình tròn trên mặt phẳng, đếm số hình tròn giao nhau

8. Cho N hình tròn trên mặt phẳng, đếm số hình tròn lồng nhau nhau

9. Bài toán búp bê Nga. http://poj.org/problem?id=3636