CONANSP - Conan Needs Help Again (Help Conan 4 )!
Giới hạn- Thời gian: 0.156s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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ồ.Example
Input: 6 4 1 0 17 12 16 10 4 16 11 2 4 8 2 3 3 2 1 16 3 15 2 8 8 10 3 5 12 8 11 6 6 10 9 15 10 9 7 4 4 6 7 9 4 6 8 5 7 Output: 5
- Người up: conankudo
- Nguồn bài: Ðố biết ^o^