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

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

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

kiennt

30 bài viết.
267 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
91 18
Mọi chuyện bắt đầu từ nắm 2013 trong quá trình xây dựng chức năng login với Facebook, tôi đã tìm ra một cách để tấn công vào các hệ thống login với...
kiennt viết 2 năm trước
91 18
White
50 4
Trong tuần vừa rồi, mình có đọc chương 7 cuốn sách (Link). Bài viết này nhằm mục đích giúp mình tổng hợp lại những kiến thức đã học được về chương ...
kiennt viết 2 tháng trước
50 4
White
29 5
1. Đặt vấn đề Một trong các vấn đề của một hệ thống backend là bài toán điều phối request tới các nguồn dữ liệu. Xét bài toán với một hệ thống bl...
kiennt viết gần 2 năm trước
29 5
Bài viết liên quan
White
44 7
Là một người thường xuyên đọc Quora, có một điểm cá nhân tôi thấy rất ấn tượng ở quora chính là khả năng autocomplete với tốc độ ánh sáng. (Ảnh) ...
huydx viết 6 tháng trước
44 7
White
3 0
What is competitive programming? Sites like CodeForces, TopCoder, HackerRank, CodeChef,... ACMICPC, Olympiad in Informatics (for high school stude...
Nguyễn Lê Vũ Long viết 12 tháng trước
3 0
White
76 34
Bài viết thuộc chủ đề nghiên cứu trong nhóm hardcore của Cộng đồng Ruby Việt Nam Đọc manga trên mobile là một nhu cầu rất lớn, nhưng hiện nay chư...
Huy Trần viết hơn 1 năm trước
76 34
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
30 bài viết.
267 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!