Vẽ bản đồ đường đồng mức
Đề bài
Mô tả
Bản đồ đường đồng mức biểu diễn địa hình của một vùng. Mỗi đường trên bản đồ đồng mức nối các điểm có cùng độ cao. Ví dụ, một bản đồ đồng mức có thể có một đường biểu diễn các điểm cao mét so với mực nước biển, một đường khác biểu diễn độ cao mét, và cứ thế.
Hiệp hội Bản đồ Đồng mức (ACM) cần một chương trình vẽ bản đồ đồng mức từ các file dữ liệu độ cao do vệ tinh thu thập. Họ đặc biệt quan tâm tới tổng độ dài của tất cả các đường đồng mức trên mỗi bản đồ. Dữ liệu độ cao là các dãy số nguyên, đo cách đều nhau dọc theo các đường quét chạy từ tây sang đông. Khoảng cách giữa các đường quét được chọn sao cho mỗi điểm đo ở phần trong của tập dữ liệu có sáu điểm lân cận gần nhất và cách đều sáu điểm đó (khi bỏ qua độ cao), như trong Hình 5 và Hình 6.
Hình 5:

Hình 6:

Quy ước của ACM là xấp xỉ địa hình thực bằng một tập các tam giác, tạo thành bằng cách nối mỗi điểm đo với các điểm lân cận gần nhất của nó bằng các đoạn thẳng. Mỗi tam giác được coi là một mặt phẳng, xác định bởi tọa độ (kể cả độ cao) của ba đỉnh. Chiếu các tam giác xuống mặt phẳng độ cao ta được một tập các tam giác đều.
Trong các hình trên, số màu đen là dữ liệu độ cao, còn các đường nét đứt và số màu đỏ là các đường đồng mức. Hình 5 có một đường đồng mức duy nhất ở độ cao . Hình 6 có nhiều đường đồng mức ở độ cao và . Một đường đồng mức có thể đi qua phần trong của một tam giác hoặc chạy dọc theo một cạnh của tam giác.
Do cách các điểm dữ liệu được xếp xen kẽ, các đường quét thứ chẵn có nhiều hơn các đường quét thứ lẻ một điểm. Trong mỗi hình, đường quét thứ nhất nằm ở trên cùng.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test, mỗi bộ là một tập dữ liệu độ cao. Mỗi bộ test bắt đầu bằng một dòng chứa bốn số nguyên:
- (): số đường quét của bộ test.
- (): số điểm đo trên mỗi đường quét thứ lẻ. Các đường quét thứ chẵn có điểm đo.
- (): khoảng cách (khi bỏ qua độ cao) từ mỗi điểm đo tới các điểm lân cận gần nhất của nó, tức là độ dài cạnh của các tam giác đều trong hình.
- (): khoảng cách độ cao giữa các đường đồng mức của bản đồ cần vẽ. Bản đồ có một đường đồng mức ở mọi nơi có độ cao là bội của . Lưu ý rằng bản đồ có thể có nhiều đường đồng mức cùng một độ cao. Ở những vùng bằng phẳng, đường đồng mức chỉ được vẽ ở biên của vùng (xem ví dụ đường đồng mức độ cao ở Hình 6).
Sau dòng đầu tiên của mỗi bộ test là các dòng chứa dữ liệu độ cao: một dãy số nguyên không âm không vượt quá . số đầu tiên là độ cao các điểm đo trên đường quét thứ nhất, từ trái sang phải. số tiếp theo là độ cao các điểm đo trên đường quét thứ hai, từ trái sang phải. Dữ liệu cứ tiếp tục như vậy, mỗi đường quét thứ lẻ có số và mỗi đường quét thứ chẵn có số, cho tới hết dữ liệu độ cao. Mỗi bộ test kết thúc bằng một dòng trống.
Dữ liệu vào kết thúc bằng một dòng chứa một số .
Dữ liệu ra
Với mỗi bộ test, in ra số thứ tự của bộ test và tổng độ dài của tất cả các đường đồng mức trên bản đồ, làm tròn đến số nguyên gần nhất, theo định dạng trong ví dụ.
Ràng buộc
- , , , .
- Mọi độ cao là số nguyên trong đoạn .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 2 5 5 1 1 1 9 1 1 1 4 4 5 3 5 7 7 5 5 9 9 9 5 9 9 9 9 7 9 9 9 7 0 |
Case 1: 15 Case 2: 54 |
Bộ 1 là Hình 5: đường đồng mức độ cao là một lục giác đều cạnh , dài . Bộ 2 là Hình 6: có các đường độ cao (hai đoạn ở hai góc trên) và độ cao (biên của vùng phẳng độ cao , kể cả phần nằm trên mép bản đồ ở hàng dưới cùng); không có điểm nào thấp hơn nên không có đường độ cao . |
| 2 1 10 2 4 4 4 2 2 4 5 5 5 0 5 10 0 |
Case 1: 30 Case 2: 12 |
Bộ 1: tam giác duy nhất phẳng ở độ cao (bội của ), đường đồng mức là biên của nó, dài . Bộ 2: tam giác giữa (hai điểm của hàng trên và điểm giữa hàng dưới) phẳng ở độ cao , cả ba cạnh của nó đều là biên vùng phẳng, tổng ; không có đường đồng mức nào đi qua phần trong của hai tam giác còn lại. |
Bình luận