Quần Đảo Pixel

Time limit: 2.0s Memory limit: 256M Read editorial

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ố:

  1. 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.
  2. 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

#InputOutput
1
6
0 0
0 1
1 1
3 3
3 3
4 4
3 16
2
8
0 0
0 1
0 2
1 0
1 2
2 0
2 1
2 2
1 16

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\).


Comments

There are no comments at the moment.

Code editor