//
you're reading...
Bài tập huấn luyện

Bài tập huấn luyện: Bản đồ mặt trăng

Sau khi phóng thành công tàu vũ trụ Thần Châu 6 vào không gian, người Trung Quốc đang tính đến một dự án lớn hơn nhiều. Đó là dư án chinh phục mặt trăng. Để dự án được thành công, người ta cần vẽ bản đồ mặt trăng ở mức thật chi tiết.

Bề mặt khu vực cần được thăm dò của mặt trăng được thể hiện bằng một bản đồ W × H. Có N địa điểm trên mặt trăng cần được ghi chú. Với mỗi điểm, người ta cần ghi chú rất nhiều thông số, vì vậy, khung ghi chú thông tin càng lớn càng tốt. Khung ghi chú phải là một hình vuông có một đỉnh trùng với điểm cần ghi chú. Một bản đồ chuẩn là bản đồ mà cả N điểm đều được ghi chú, mỗi khung ghi chú có cạnh tối thiểu là 1. Các khung ghi chú không được chồng lên nhau mà chỉ được kề cạnh với nhau. Các khung ghi chú cũng không được có phần nào nằm ở phía ngoài bản đồ.

Bạn hãy giúp các nhà khoa học tìm cách ghi chú trên bản đồ sao cho số lượng thông tin ghi được nhiều nhất có thể. Một phương án được xem xét độ tốt bằng tổng diện tích các khung ghi chú phủ trên bề mặt bản đồ.

Input: MOONMAP.INP

  • Dòng đầu tiên ghi 3 số nguyên dương W, H, N.
  • N dòng tiếp theo ghi tọa độ xi, yi của N điểm cần được ghi chú. Các tọa độ đều là số nguyên.

Output: MOONMAP.OUT

  • Gồm N dòng, mỗi dòng ghi số nguyên K và xâu S. Số K là độ dài cạnh hình vuông còn xâu S là hướng của hình vuông với ý nghĩa như sau:
  • NW nếu điểm cần chú thích nằm ở góc trái trên của hình vuông.
  • SW nếu điểm cần chú thích nằm ở góc trái dưới của hình vuông.
  • NE nếu điểm cần chú thích nằm ở góc phải trên của hình vuông.
  • SE nếu điểm cần chú thích nằm ở góc phải dưới của hình vuông.

Giới hạn:

  • 1 ≤ N ≤ 1000
  • 0 < W ≤ 106
  • 0 < H ≤ 106
  • 0 ≤ xi ≤ W.
  • 0 ≤ yi ≤ H.
  • Thời gian: 1 s/test
  • Bộ nhớ: 16 MB

Ví dụ:

MOONMAP.INP MOONMAP.OUT
4 4 3

3 1

3 3

1 4

1 NW

3 NE

1 NW

(Với cách làm như trên, diện tích phủ là 11)

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Danh mục

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Merle running

Sentinels

Papilio Machaon...

More Photos

Thống kê

  • 136,495 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: