Quần Đảo Pixel
Problem
Em gái của Khoa là Bông đang mê mẩn trò chơi "Pixel Ocean". Bản đồ của trò chơi là một lưới ô vuông vô hạn, mỗi ô được xác định bởi cặp tọa độ nguyên \((x, y)\). Ban đầu mọi ô đều là nước. Mỗi lần Bông chạm vào một ô \((x, y)\), ô đó biến thành đất. Chạm lại vào một ô đã là đất thì không có gì thay đổi.
Sau khi Bông chạm \(n\) lần, trò chơi sẽ chấm điểm dựa trên hai con số:
- Số hòn đảo. Hai ô đất được coi là liền nhau nếu chúng chung một cạnh. Hai ô chỉ chạm nhau ở góc thì không liền nhau. Một hòn đảo là một nhóm ô đất mà từ ô bất kỳ có thể đi tới mọi ô khác trong nhóm, mỗi bước đi sang một ô đất liền nhau.
- Tổng chiều dài bờ biển. Mỗi ô có \(4\) cạnh, mỗi cạnh dài \(1\) đơn vị. Một cạnh của ô đất được tính là bờ biển nếu ở phía bên kia cạnh đó là một ô nước. Lưu ý: nước nằm bên trong một hòn đảo (tức là hồ) vẫn là nước, nên bờ hồ cũng được tính là bờ biển.
Không may, bản cập nhật mới nhất làm trò chơi tính sai cả hai con số và Bông thì đang khóc vì bị điểm thấp. Khoa nhờ bạn viết lại phần tính điểm.
"Bản đồ thì vô hạn, nhưng bộ nhớ máy tính thì không."
-- Khoa, sau khi thử tạo một mảng hai chiều kích thước \(2 \cdot 10^9 \times 2 \cdot 10^9\)
Input
- Dòng đầu tiên gồm một số nguyên \(n\) \((1 \leq n \leq 2 \times 10^5)\) là số lần Bông chạm vào bản đồ.
- \(n\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(x, y\) \((-10^9 \leq x, y \leq 10^9)\) là tọa độ ô được chạm. Một ô có thể được chạm nhiều lần.
Output
- In ra trên một dòng hai số nguyên: số hòn đảo và tổng chiều dài bờ biển.
Sample
| # | Input | Output |
|---|---|---|
| 1 | | |
| 2 | | |
Note
Sample 1: ô \((3, 3)\) bị chạm hai lần nhưng vẫn chỉ là một ô đất. Có \(5\) ô đất:
- \((0, 0), (0, 1), (1, 1)\) liền nhau thành một hòn đảo hình chữ L. Ba ô có \(12\) cạnh, trong đó \(2\) cặp ô liền nhau "che" mất \(4\) cạnh, còn lại \(8\) đơn vị bờ biển.
- \((3, 3)\) và \((4, 4)\) chỉ chạm nhau ở góc nên là hai hòn đảo riêng, mỗi hòn có \(4\) đơn vị bờ biển.
Tổng cộng \(3\) hòn đảo và \(8 + 4 + 4 = 16\) đơn vị bờ biển.
Sample 2: tám ô tạo thành một vòng khép kín bao quanh ô nước \((1, 1)\). Đây là một hòn đảo có hồ ở giữa. Bờ biển phía ngoài dài \(12\), bờ hồ phía trong dài \(4\), tổng cộng \(16\).
Code editor
Sign in to write and submit your solution.
Log in
Comments