USACO 2016 - US Open - Hạng Bạc

\(N\) con bò của Farmer John (\(5 \leq N \leq 50\,000\)) đều đứng tại các vị trí phân biệt trên cánh đồng hai chiều của ông. FJ muốn bao quanh tất cả đàn bò bằng một hàng rào hình chữ nhật có các cạnh song song với trục \(x\) và trục \(y\), đồng thời muốn hàng rào này nhỏ nhất có thể nhưng vẫn chứa mọi con bò (bò được phép đứng trên biên).

Không may, FJ đang có ngân sách eo hẹp vì sản lượng sữa thấp trong quý trước. Do đó, nếu có thể, ông muốn xây một khu vực có hàng rào bao quanh còn nhỏ hơn nữa và sẵn sàng bán tối đa ba con bò trong đàn để thực hiện điều này.

Hãy giúp FJ tính diện tích nhỏ nhất có thể bao quanh bằng hàng rào sau khi loại tối đa ba con bò khỏi đàn (rồi xây hàng rào khít nhất bao quanh những con bò còn lại).

Trong bài này, hãy coi bò là các điểm và hàng rào là tập hợp gồm bốn đoạn thẳng (tức là đừng coi bò là các "hình vuông đơn vị"). Lưu ý rằng đáp án có thể bằng không, chẳng hạn nếu tất cả những con bò còn lại cùng đứng trên một đường thẳng đứng hoặc ngang.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên xác định vị trí của một con bò. Tọa độ của bò là các số nguyên dương trong khoảng \(1 \ldots 40\,000\).

Dữ liệu ra

In một số nguyên duy nhất biểu thị diện tích nhỏ nhất mà FJ có thể bao quanh bằng hàng rào sau khi loại khỏi đàn tối đa ba con bò được lựa chọn cẩn thận.

Ví dụ

6
1 1
7 8
10 9
8 12
4 100
50 7

12

Nguồn

USACO 2016 US Open Contest, Silver - Field Reduction: https://usaco.org/index.php?page=viewproblem2&cpid=642

Tác giả: Brian Dean.

Bessie, cô bò vốn luôn yêu thích những vật lấp lánh, đã bắt đầu theo đuổi sở thích khai thác kim cương vào thời gian rảnh! Cô đã thu thập được \(N\) viên kim cương (\(N \leq 50\,000\)) với nhiều kích thước khác nhau và muốn sắp xếp một số viên vào hai tủ trưng bày trong chuồng.

Vì Bessie muốn những viên kim cương trong từng tủ có kích thước tương đối giống nhau, cô quyết định không đặt hai viên kim cương vào cùng một tủ nếu kích thước của chúng chênh lệch quá \(K\) (hai viên kim cương có thể được trưng bày trong cùng một tủ nếu kích thước của chúng chênh lệch đúng bằng \(K\)). Cho \(K\), hãy giúp Bessie xác định tổng số viên kim cương tối đa mà cô có thể trưng bày trong cả hai tủ.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\) (\(0 \leq K \leq 1\,000\,000\,000\)). Mỗi dòng trong \(N\) dòng tiếp theo chứa một số nguyên biểu thị kích thước của một viên kim cương. Mọi kích thước đều là số dương và không vượt quá \(1\,000\,000\,000\).

Dữ liệu ra

In một số nguyên dương duy nhất cho biết tổng số viên kim cương tối đa mà Bessie có thể trưng bày trong cả hai tủ.

Ví dụ

7 3
10
5
1
12
9
5
14

5

Nguồn

USACO 2016 US Open Contest, Silver - Diamond Collector: https://usaco.org/index.php?page=viewproblem2&cpid=643

Tác giả: Nick Wu và Brian Dean.

Farmer John và đàn bò dự định rời thị trấn để đi nghỉ dài ngày, vì vậy FJ muốn tạm thời đóng cửa trang trại nhằm tiết kiệm tiền trong thời gian đó.

Trang trại gồm \(N\) chuồng được nối với nhau bởi \(M\) đường đi hai chiều giữa một số cặp chuồng (\(1 \leq N, M \leq 3000\)). Để đóng cửa trang trại, FJ dự định mỗi lần đóng một chuồng. Khi một chuồng đóng cửa, tất cả các đường đi kề với chuồng đó cũng đóng và không thể được sử dụng nữa.

FJ muốn biết tại mỗi thời điểm (ban đầu và sau mỗi lần đóng cửa) liệu trang trại có "liên thông hoàn toàn" hay không — nghĩa là có thể đi từ bất kỳ chuồng đang mở nào đến bất kỳ chuồng đang mở nào khác theo một dãy đường đi thích hợp. Vì trang trại của FJ ban đầu đang trong tình trạng phần nào xuống cấp, nó thậm chí có thể không liên thông hoàn toàn ngay từ đầu.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\). Mỗi dòng trong \(M\) dòng tiếp theo mô tả một đường đi bằng cặp chuồng mà nó nối (các chuồng được đánh số thuận tiện từ \(1 \ldots N\)). \(N\) dòng cuối cùng cho một hoán vị của \(1 \ldots N\), mô tả thứ tự các chuồng sẽ bị đóng cửa.

Dữ liệu ra

Kết quả gồm \(N\) dòng, mỗi dòng chứa YES hoặc NO. Dòng đầu tiên cho biết trang trại ban đầu có liên thông hoàn toàn hay không, và dòng \(i+1\) cho biết trang trại có liên thông hoàn toàn hay không sau lần đóng cửa thứ \(i\).

Ví dụ

4 3
1 2
2 3
3 4
3
4
1
2

YES
NO
YES
YES

Nguồn

USACO 2016 US Open Contest, Silver - Closing the Farm: https://usaco.org/index.php?page=viewproblem2&cpid=644

Tác giả: Yang Liu.