USACO 2012 - Tháng 12 - Hạng Bạc

Sau khi ghé thăm một bảo tàng nghệ thuật hiện đại, Farmer John quyết định thiết kế lại trang trại bằng cách di chuyển toàn bộ \(N\) (\(1 \le N \le 1000\)) hàng rào giữa các đồng cỏ! Mỗi hàng rào được mô tả bởi một đoạn thẳng trên mặt phẳng hai chiều. Nếu hai hàng rào gặp nhau thì chúng chỉ gặp tại các đầu mút. Mỗi hàng rào chạm đúng hai hàng rào khác, một hàng rào tại mỗi đầu mút.

FJ có \(C\) con bò (\(1 \le C \le 1000\)) trong trang trại. Mỗi con bò ở tại một điểm trên mặt phẳng hai chiều không nằm trên bất kỳ hàng rào nào, và không có hai con bò nào ở cùng một điểm. Hai con bò được xem là thuộc cùng một cộng đồng nếu một con có thể đi đến con kia mà không chạm vào bất kỳ hàng rào nào. Hãy giúp FJ xác định số lượng bò trong cộng đồng lớn nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(C\), cách nhau bởi dấu cách.
• \(N\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1, y_1, x_2, y_2\), mô tả một hàng rào từ điểm \((x_1, y_1)\) đến điểm \((x_2, y_2)\). Mọi tọa độ đều là số nguyên trong khoảng từ \(0\) đến \(1\,000\,000\).
• \(C\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\), mô tả vị trí của một con bò. Mọi tọa độ đều là số nguyên trong khoảng từ \(0\) đến \(1\,000\,000\).

Dữ liệu ra

In ra số lượng bò trong cộng đồng lớn nhất.

Ví dụ

10 4
0 0 10 0
10 0 10 10
0 0 0 10
10 10 0 10
8 8 9 8
9 8 8 9
8 9 8 8
2 7 3 2
3 2 7 5
7 5 2 7
15 3
1 4
4 5
7 1

2

Nguồn

USACO 2012 December Contest, Silver — Problem 1: Crazy Fences

Tác giả đề: Brian Dean, 2012.

\(N\) con bò của Farmer John (\(1 \le N \le 2000\)) đang đứng tại nhiều vị trí khác nhau dọc theo con đường thẳng từ chuồng đến đồng cỏ, có thể xem như một trục số một chiều. Vì những con bò thích giữ liên lạc với nhau qua thư điện tử, FJ muốn lắp đặt các trạm phát Wifi tại nhiều vị trí sao cho tất cả bò đều được phủ sóng không dây.

Sau khi tham khảo giá, FJ biết rằng chi phí của một trạm phát Wifi phụ thuộc vào khoảng cách mà nó có thể truyền tín hiệu: một trạm phát có công suất \(r\) tốn \(A + B \cdot r\), trong đó \(A\) là chi phí cố định để lắp đặt trạm và \(B\) là chi phí trên mỗi đơn vị khoảng cách truyền tín hiệu. Nếu FJ lắp một thiết bị như vậy tại vị trí \(x\), nó có thể truyền dữ liệu đến mọi con bò nằm trong khoảng từ \(x-r\) đến \(x+r\). Trạm phát có công suất truyền \(r=0\) vẫn được phép, nhưng khi đó nó chỉ phủ sóng cho một con bò ở đúng vị trí của trạm phát.

Cho các giá trị \(A\), \(B\) và vị trí của những con bò, hãy xác định phương án ít tốn kém nhất để FJ phủ sóng không dây cho tất cả bò.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên \(N\), \(A\) và \(B\), cách nhau bởi dấu cách (\(0 \le A, B \le 1000\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên trong khoảng từ \(0\) đến \(1\,000\,000\), mô tả vị trí của một con bò của FJ.

Dữ liệu ra

In ra chi phí nhỏ nhất để phủ sóng không dây cho tất cả bò.

Ví dụ

3 20 5
7
0
100

57.5

Nguồn

USACO 2012 December Contest, Silver — Problem 2: Wifi Setup

Tác giả đề: Brian Dean, 2012.

Trang trại của Farmer John có một mạng lưới cũ gồm \(M\) đường ống (\(1 \le M \le 500\)) để bơm sữa từ chuồng đến bể chứa sữa. Trong năm tới, ông muốn dỡ bỏ và nâng cấp phần lớn số đường ống này, nhưng vẫn muốn giữ nguyên các đường ống thuộc đúng một đường đi để tiếp tục bơm sữa từ chuồng đến bể chứa.

Mạng lưới đường ống được mô tả bởi \(N\) điểm nối (\(1 \le N \le 500\)), mỗi điểm có thể là đầu mút của một tập hợp các đường ống. Điểm nối \(1\) là chuồng, còn điểm nối \(N\) là bể chứa. Mỗi đường ống trong số \(M\) đường ống hai chiều nối một cặp điểm nối, đồng thời có một độ trễ (lượng thời gian để sữa đi từ đầu này đến đầu kia của đường ống) và một dung lượng (lượng sữa trên mỗi đơn vị thời gian có thể được bơm ổn định qua đường ống). Có thể có nhiều đường ống nối cùng một cặp điểm nối.

Đối với một đường đi gồm các đường ống nối từ chuồng đến bể, độ trễ của đường đi là tổng độ trễ của các đường ống trên đó, còn dung lượng của đường đi là giá trị nhỏ nhất trong các dung lượng của các đường ống trên đó (vì đây là "nút thắt cổ chai" giới hạn tốc độ tổng thể mà sữa có thể được bơm qua đường đi). Nếu FJ muốn gửi tổng cộng \(X\) đơn vị sữa qua một đường đi có độ trễ \(L\) và dung lượng \(C\), thời gian cần thiết vì thế là \(L + X/C\).

Với cấu trúc mạng lưới đường ống của FJ, hãy giúp ông chọn một đường đi duy nhất từ chuồng đến bể chứa sao cho có thể bơm \(X\) đơn vị sữa trong tổng thời gian nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(X\), cách nhau bởi dấu cách (\(1 \le X \le 1\,000\,000\)).
• \(M\) dòng tiếp theo, mỗi dòng mô tả một đường ống bằng bốn số nguyên \(I\), \(J\), \(L\), \(C\). \(I\) và \(J\) (\(1 \le I, J \le N\)) là các điểm nối ở hai đầu đường ống. \(L\) và \(C\) (\(1 \le L, C \le 1\,000\,000\)) lần lượt là độ trễ và dung lượng của đường ống.

Dữ liệu ra

In ra lượng thời gian nhỏ nhất để FJ gửi sữa dọc theo một đường đi duy nhất, làm tròn xuống số nguyên gần nhất.

Ví dụ

3 3 15
1 2 10 3
3 2 10 2
1 3 14 1

27

Nguồn

USACO 2012 December Contest, Silver — Problem 3: Milk Routing

Tác giả đề: Brian Dean, 2012.