RÀO RUỘNG PHÚ ÔNG CHO RẰNG BỜM KHÔNG BIẾT TÍNH TOÁN VÀ THÍCH TR...
Bài 2. Rào ruộng
Phú ông cho rằng Bờm không biết tính toán và thích trêu Bờm. Lần này, khi thuê Bờm chăng
dây rào ruộng cho mình, Phú ông hứa sẽ cho Bờm thửa ruộng to nhất nếu Bờm đáp ứng được
yêu cầu đặt ra. Phú ông có N thửa ruộng được đánh số từ 1 đến N, nằm trong vùng đất có hai
đường cái vuông góc với nhau mà ta có thể hình dung như một mặt phẳng với hai trục tọa độ.
Bờ đắp quanh mỗi thửa ruộng có thể xem như một đường gấp khúc khép kín không tự cắt và
đặc biệt ở chỗ các cạnh đều song song với các trục tọa độ. Bờm sẽ phải đem dây chăng dọc
theo các bờ, viền quanh mỗi thửa ruộng. Gọi CX, CY tương ứng là chu vi của hai thửa ruộng
X, Y, nếu CX là ước số của CY thì để rào cho X và
Y, Bờm chỉ cần mang loại dây có độ dài
CY. Phú ông yêu cầu Bờm cho biết cần mang ít nhất bao nhiêu loại dây để rào N thửa ruộng
đó (hai đoạn dây có độ dài khác nhau thuộc hai loại khác nhau và ngược lại hai đoạn dây
khác loại thì có độ dài khác nhau).
Yêu cầu: Hãy xác
định giúp Bờm số loại dây ít
nhất cần chuẩn bị.
Dữ liệu: Vào từ file văn bản PERIM.INP:
Dòng
đầu tiên ghi số nguyên dương
N
(1≤N≤ 200) là số lượng thửa ruộng của Phú
ông;
Dòng thứ i trong N dòng tiếp theo mô tả thửa
ruộng thứ i: đầu tiên là k
i
(4 ≤ k
i
≤ 200) là số
lượng đỉnh của ruộng thứ i (1
≤ i
≤ N), tiếp
theo là k
i
cặp tọa độ của các đỉnh được liệt kê
chỉ theo một chiều nào
đó đi vòng quanh
hình (các tọa độ là các số nguyên có trị tuyệt
đối không quá 20000).
Kết quả: Ghi ra file văn bản PERIM.OUT theo qui cách sau:
Dòng đầu là một số nguyên dương M, đó là số loại dây.
Trong dòng tiếp theo, độ dài của M loại dây được đưa ra theo thứ tự giảm dần.
Ví dụ:
PERIM.INP
PERIM.OUT
5
3
36 20 14
12 -2 0 -2 2 0 2 0 4 2 4 2 6 4 6 4 8 6 8 6 2 8 2 8 0
12 1 -3 1 -2 2 -2 2 -1 3 -1 3 -4 4 -4 4 -5 -1 -5 -1 -4 0 -4 0 -3
10 8 -4 8 -3 7 -3 7 -2 5 -2 5 -4 6 -4 6 -5 9 -5 9 -4
10 11 2 12 2 12 7 11 7 11 8 8 8 8 6 10 6 10 5 11 5
6 9 -2 9 1 11 1 11 -1 12 -1 12 -2