USACO 2019 - Tháng 1 - Hạng Bạc

Đã đến thời điểm Farmer John gieo cỏ trên tất cả các cánh đồng của mình. Toàn bộ trang trại gồm \(N\) cánh đồng (\(1 \leq N \leq 10^5\)), được đánh số thuận tiện từ \(1 \ldots N\) và nối với nhau một cách thuận tiện bằng \(N-1\) lối đi hai chiều sao cho từ mọi cánh đồng đều có thể đến mọi cánh đồng khác qua một số lối đi.

Farmer John có thể gieo một loại cỏ khác nhau trên mỗi cánh đồng, nhưng ông muốn giảm thiểu tổng số loại cỏ sử dụng, vì càng dùng nhiều loại cỏ thì chi phí càng cao.

Thật không may, những con bò của ông đã trở nên khá kén chọn đối với các loại cỏ trong trang trại. Nếu cùng một loại cỏ được gieo trên hai cánh đồng kề nhau (được nối trực tiếp bằng một lối đi), hoặc thậm chí trên hai cánh đồng gần kề (cả hai đều được nối trực tiếp bằng các lối đi đến cùng một cánh đồng), các cô bò sẽ phàn nàn vì các lựa chọn ăn uống thiếu đa dạng. Với những trò nghịch ngợm mà chúng thường gây ra khi không hài lòng, điều cuối cùng Farmer John cần là những con bò phàn nàn.

Hãy giúp Farmer John xác định số loại cỏ tối thiểu cần dùng cho toàn bộ trang trại.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N-1\) dòng còn lại mô tả một lối đi bằng hai cánh đồng mà nó kết nối.

Dữ liệu ra

In ra số loại cỏ tối thiểu mà Farmer John cần sử dụng.

Ví dụ

4
1 2
4 3
2 3

3

Nguồn

Đề bài gốc: USACO 2019 January Contest, Silver — Grass Planting

Tác giả: Dhruv Rohatgi

Ngôi làng CLA có rất nhiều ao hồ. Sơ đồ địa lí ngôi làng biểu diễn bằng một bảng ô vuông \(N \times N\). Mỗi ô vuông được biểu diễn bằng một trong hai kí tự:

• . - cho biết vị trí này là ô đất.
• # - biểu thị vị trí này là ô nước.

Một cái ao làng được xác định bằng một vùng các ô vuông #. Hai ô vuông # \(A, B\) thuộc cùng một ao, khi và chỉ khi từ ô \(A\) có thể chèo thuyền qua các ô # sang ô \(B\) và ngược lại, bằng cách di chuyển theo bốn hướng Đông, Tây, Nam, Bắc. Diện tích của ao được xác định bằng số lượng ô vuông thuộc cái ao đó. Chu vi của ao được xác định bằng tổng các ô đất . hoặc đường biên kề cạnh của mỗi ô thuộc cái ao này.

Để chọn một cái ao cho lễ hội năm nay của làng. Trưởng làng đặt yêu cầu cái ao phải có diện tích càng lớn càng tốt, và nếu có nhiều ao cùng diện tích thì chu vi càng nhỏ càng tốt. Do đó, bạn hãy giúp trưởng làng xác định diện tích và chu vi cái ao này nhé.

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \le N \le 1000)\)
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) kí tự, mô tả sơ đồ ngôi làng. Các kí tự có thể là . hoặc #.

Output

• In ra diện tích và chu vi của cái ao được chọn thỏa mãn yêu cầu của trưởng làng.

Example

6
##....
....#.
.#..#.
.#####
...###
....##

13 22 

Từ đồng cỏ của mình trong trang trại, cô bò Bessie có một tầm nhìn tuyệt đẹp ra dãy núi ở đường chân trời. Dãy núi có \(N\) ngọn núi (\(1 \leq N \leq 10^5\)). Nếu coi trường nhìn của Bessie là mặt phẳng \(xy\), mỗi ngọn núi là một tam giác có đáy nằm trên trục \(x\). Hai cạnh bên của ngọn núi đều tạo với đáy góc \(45\) độ, nên đỉnh núi tạo thành một góc vuông. Vì vậy, ngọn núi \(i\) được mô tả chính xác bởi vị trí đỉnh \((x_i, y_i)\). Không có hai ngọn núi nào có vị trí đỉnh hoàn toàn giống nhau.

Bessie đang cố đếm tất cả các ngọn núi, nhưng vì chúng đều có màu gần giống nhau, cô không thể nhìn thấy một ngọn núi nếu đỉnh của nó nằm trên biên hoặc bên trong hình tam giác của bất kỳ ngọn núi nào khác.

Hãy xác định số đỉnh phân biệt, và do đó là số ngọn núi, mà Bessie có thể nhìn thấy.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng còn lại chứa \(x_i\) (\(0 \leq x_i \leq 10^9\)) và \(y_i\) (\(1 \leq y_i \leq 10^9\)), mô tả vị trí đỉnh của một ngọn núi.

Dữ liệu ra

In ra số ngọn núi mà Bessie có thể phân biệt được.

Ví dụ

3
4 6
7 2
2 5

2

Nguồn

Đề bài gốc: USACO 2019 January Contest, Silver — Mountain View

Tác giả: Brian Dean