Lại nói sau trận đấu với Thu Uyên,Conan đã giành chiến thắng và phần thưởng của anh là 100 điểm trên ioitrain và một chuyến đi du lịch Hawai ( căn bản Thu Uyên cũng rân chơi nên đặt cược hơi cao quá
,giờ chỉ có ngậm ngùi thôi ) . Conan vội vàng lên đường không quên mang theo 10 suất KFC Combo 1 ( vì nghe nói ở Hawai không bán KFC
)
Hawai là một hòn đảo giữa đại dương bao la. Trên hòn đào có các hồ và trên những hồ này lại có những hòn đảo nhỏ mà trên đó có thể có hồ mà trên đó có thể có những hòn đảo nhỏ nữa và tương tự…. Đại dương có bậc là 0, Hawai có bậc 1. Hồ trên Hawai có bậc 2. Như vậy, một hồ có bậc w+1 nếu nó ở trên hòn đảo có bậc w và một đảo có bậc j+1 nếu nó nằm trên hồ có bậc j. Tất cả các hồ và đảo có biên là đa giác không tự cắt với các cạnh liên tiếp vuông góc với nhau (// với trục OX hoặc OY) và đỉnh có tọa độ nguyên. Tất nhiên các đường biên của hồ hay đảo không cắt nhau. Conan vốn thích sự yên tĩnh nên cậu muốn biết nơi nào có bậc cao nhất. Yêu cầu tính bậc cao nhất của đảo hay hồ ở Hawai.
Input
Dòng đầu ghi n, là số đường giới hạn (1 <= n <= 40000). Các đường biên được mô tả trong các dòng tiếp theo, mỗi dòng một đường biên. Số đầu tiên trong mỗi dòng đó ghi số chẵn k là số điểm tạo nên đường biên, 4 <= k <= 10000. Tiếp theo là k số x1, x2, …, xk, 0 <= xi <= 10^8. Các điểm tạo nên đường biên là (x1, x2), (x3, x2), (x3, x4) …, (xk-1, xk), (x1, xk). Các điểm này được đặt trong tọa độ Đề Các và ngược chiều kim đồng hồ. Các đường biên được in theo thứ tự thỏa mãn đường biên của mỗi hồ được in sau đường biên hòn đảo chứa nó và đường biên của mỗi hòn đảo được in sau đường biên của hồ bao quanh nó. Chú ý: không cần dùng quá 200000 điểm để mô tả bản đồ.
Output
Dòng duy nhất ghi bậc lớn nhất của hòn đảo hay hồ.
Những câu chưa hiểu ?
"là số đường giới hạn (1 <= n <= 40000)"
"ngược chiều kim đồng hồ"
"Các đường biên được in theo thứ tự thỏa mãn đường biên của mỗi hồ được in sau đường biên hòn đảo chứa nó và đường biên của mỗi hòn đảo được in sau đường biên của hồ bao quanh nó."
Công ti phần mềm FSoft mới nhận thêm N nhân viên. Lãnh đạo công ti muốn số nhân viên mới trên chia thành M nhóm khác nhau thỏa mãn rằng: số người trong các nhóm bằng nhau, mỗi người chỉ thuộc một nhóm. Qua phân tích bản CV và lúc phỏng vấn, công ti đưa ra bảng đánh giá A với Aij là sự hiệu quả khi người thứ i và j thuộc cùng một nhóm.
Ban lãnh đạo công ti nhờ bạn tìm cách phân chia N nhân viên thành M nhóm sao cho hiệu quả nhất. Sự hiệu quả của một cách phân chia bằng tổng sự hiệu quả của từng nhóm; sự hiệu quả của mỗi nhóm bằng tổng sự hiệu của của các cặp trong nhóm đó.
Dữ liệu
- Dòng đầu tiên chứa hai số N, M.
- N dòng tiếp theo, mỗi dòng ghi N số mô tả bảng A. (Aii=0; Aji=Aij)
Kết quả
- Dòng đầu tiên ghi sự hiệu quả của cách phân chia mà bạn tìm được.
- M dòng tiếp theo ghi danh sách nhân viên của mỗi nhóm trong cách chia của bạn.