Strict Standards: call_user_func_array() expects parameter 1 to be a valid callback, non-static method HTML_content::show() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/includes/Cache/Lite/Function.php on line 98

Strict Standards: Non-static method HTML_content::_Itemid() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 452

Strict Standards: Non-static method HTML_content::_linkInfo() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 455

Strict Standards: Non-static method SAXY_Parser_Base::parseAttributes() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/mambots/content/geshi.php on line 57

Strict Standards: Non-static method HTML_content::Title() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 470

Strict Standards: Non-static method HTML_content::PdfIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 473

Strict Standards: Non-static method mosHTML::PrintIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 476

Strict Standards: Non-static method mosAdminMenus::ImageCheck() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/includes/joomla.php on line 2329

Strict Standards: Non-static method HTML_content::EmailIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 479
Nữ thần Artemis
Strict Standards: Non-static method HTML_content::EditIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 632

Strict Standards: Non-static method HTML_content::Section_Category() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 511

Strict Standards: Non-static method HTML_content::Section() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 755

Strict Standards: Non-static method HTML_content::Category() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 758

Strict Standards: Non-static method HTML_content::Author() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 514

Strict Standards: Non-static method HTML_content::CreateDate() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 517

Strict Standards: Non-static method HTML_content::URL() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 520

Strict Standards: Non-static method HTML_content::ModifiedDate() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 536

Strict Standards: Non-static method HTML_content::ReadMore() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 539
Người viết: Ngô Minh Đức   
10/04/2008

Strict Standards: Non-static method HTML_content::TOC() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 526
Bài Nữ thần Artemis

Thần Dớt giao cho nữ thần Artemis cai quản một vùng đất hình chữ nhật để trồng rừng. Hình chữ nhật nẳm trong góc phần tư thứ nhất trong hệ trục toạ độ, với các cạnh là các đoạn thẳng nằm trên các trục toạ độ, góc dưới trái của hình chữ nhật trùng với gốc toạ độ. Nữ thần chỉ được trồng cây tại những vị trí có toạ độ nguyên nằm trong hình chữ nhật. Artemis muốn các cây được trồng như mọc tự nhiên vì thế nữ thần trồng các cây sao cho một đường thẳng nối hai cây không bao giờ song song với các trục toạ độ.

Một lần thần Dớt muốn Artemis chặt các cây cho ông ta. Các cây được chặt theo cách sau:
- Chặt tối thiểu T cây.
- Nhằm tạo một sân bóng hình chữ nhật trong tương lai, Artemis chỉ được phép chặt các cây trong hình chữ nhật có các cạnh song song với các trục toạ độ.
- 2 góc đối diện cuả hình chữ nhật phải có cây. Do vậy các cây này cũng bị chặt.

Vì rất yêu thích các cây, nên nữ thần chỉ muốn chặt các cây với số lượng ít nhất. Cho trước những thông tin về khu rừng và số cây T tối thiểu cần chặt. Bạn hãy viết chương trình đưa ra vùng cây cần chặt cho Artemis.

INPUT
Dữ liệu được cho trong file artemis.in
- Dòng đầu tiên chứa số nguyên N (1≤ N ≤ 20000) là số cây trong rừng.
- Dòng thứ hai chứa số nguyên T (1< T ≤ N) là số cây tối thiểu cần chặt.
- N dòng tiếp theo mô tả vị trí của N cây. Mỗi một dòng gồm hai số nguyên X,Y (0≤X,Y≤64000) là toạ độ của cây.

OUTPUT
Kết quả được đưa ra trong file artemis.out. File gồm một dòng chứa 2 số nguyên i,j cách nhau bởi khoảng trắng: cây thứ i (tương ứng với dòng i+2 trong file input) và cây thứ j tương ứng với dòng j+2 trong file input) là hai vị trí góc đối diện của vùng cây bị chặt. Thứ tự của hai số này độc lập với nhau. Nếu có nhiều phương án bạn chỉ cần đưa ra một phương án.
Ví dụ:
 

 
artermis.inp
3
2
1 1
2 3
5 6
artemis.out
1 2
 
Strict Standards: Non-static method HTML_content::Navigation() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 550

Strict Standards: Non-static method mosHTML::CloseButton() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 553

Strict Standards: Non-static method mosHTML::BackButton() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 556