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
2. Tảo biển In E-mail
(5 votes)
Người viết: Ngô Minh Đức   
20/06/2008

Bài 2. Tảo biển

Tảo biển đóng một vai trò hết sức quan trọng trong quá trình đảm bảo cân bằng sinh thái trên trái đất. Khả năng hấp thụ CO2 của nó vượt xa khả năng tương ứng ở tất cả các cánh rừng nhiệt đới trên thế giới.

Tảo là thức ăn chủ yếu của nhiều loại sinh vật biển và một số tảo cũng có mặt trên bàn ăn của con người. Vì vậy, sự phân bố và phát triển của tảo trên bề mặt đại dương được theo dõi chặt chẽ từ ngoài không gian. Các vệ tinh sinh thái thường xuyên chụp và gửi về trái đất bản đồ vùng tảo phát triển. Mỗi vùng có mật độ tảo cao được gọi là cánh đồng tảo. Một số thông tin về các cánh đồng tảo được Liên hợp quốc bán cho các quốc gia quan tâm ở ba mức:

·         Mức 1 (Đầy đủ): bao gồm dữ liệu và hệ thống xử lý,

·         Mức 2 (Kết quả): thông tin được xử lý và kết quả được chuyển giao cho người mua,

·         Mức 3 (Thông tin sơ cấp): người mua nhận được thông tin ở dạng sơ cấp, chưa qua xử lý.

Dĩ nhiên giá bán ở mức 3 là thấp nhất. Công ty SEAFOOD có đội tàu viễn dương khá lớn nhưng cũng chỉ đủ kinh phí mua thông tin mức 3. Thông tin mà Công ty mua là bản đồ cánh đồng tảo ở khu vực nhiệt đới Thái Bình Dương có dạng là một miền được bao bởi đường gấp khúc khép kín không tự cắt, có các cạnh song song với trục tọa độ và được xác định bởi tọa độ các đỉnh của nó.  Các đỉnh được liệt kê theo một chiều nào đó đi vòng quanh đường gấp khúc và không có 3 đỉnh liên tiếp nào thẳng hàng. Tọa độ các đỉnh đều là những số nguyên không âm, nhưng cho ở dạng nguyên thủy: giá trị các tọa độ của hai điểm liên tiếp được viết liên tục trên một dòng không có ký tự phân cách tạo thành một xâu ký tự số.

Ví dụ, bản đồ tảo ở hình 1 có tọa độ các đỉnh là (1,2), (1,5), (3,5), (3,7), (6,7), (6,4), (8,4), (8,1), (3,1) và (3,2). Nếu các đỉnh được liệt kê theo chiều kim đồng hồ thì thông tin Công ty nhận được là:

1215

3537

6764

8481

3132

Mỗi phòng của Công ty cần một số loại thông tin. Bạn là nhân viên của Phòng Kế hoạch và ở đó người ta yêu cầu bạn cho biết chu vi d và diện tích S của cánh đồng. Nhà cung cấp thông tin cho biết số đỉnh của đường gấp khúc không quá 200000, giá trị tọa độ mỗi đỉnh không vượt quá 109. Dữ liệu đảm bảo chính xác.

Dữ liệu: Vào từ file văn bản SEAWEED.INP gồm:

·         Dòng đầu tiên chứa số nguyên dương n cho biết số đỉnh của đường gấp khúc,

·         Mỗi dòng trong các dòng tiếp theo chứa một xâu chỉ chứa các ký tự số thập phân ứng với một dòng thông tin về các đỉnh của đường gấp khúc mà công ty đã nhận được. Thông tin về các đỉnh được liệt kê theo một chiều nào đó (theo chiều kim đồng hồ hoặc ngược lại).

Dữ liệu cho đảm bảo tồn tại duy nhất một đường gấp khúc thoả mãn điều kiện bài toán.

Kết quả: Ghi ra file văn bản SEAWEED.OUT, gồm một dòng chứa 2 số nguyên dS, ghi cách nhau một dấu cách.

Ví dụ:

SEAWEED.INP

SEAWEED.OUT

10

1215

3537

6764

8481

3132

26 30

 
< Trước   Tiếp >