Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
Nữ thần Artemis In E-mail
(2 votes)
Người viết: Ngô Minh Đức   
10/04/2008
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
 
< Trước   Tiếp >