Họa sĩ
Đề bài
Mô tả
Có lẽ bạn chưa bao giờ nghe nói đến họa sĩ Peer. Ông không nổi tiếng lắm, và đó là điều ông rất lấy làm tiếc. Peer là một trong những người sáng lập trường phái đơn sắc: mỗi bức tranh của ông chỉ dùng một màu duy nhất, nhưng với nhiều sắc độ đậm nhạt khác nhau. Ông cũng tin vào việc dùng các hình hình học đơn giản.
Trong thời kỳ tam giác, Peer vẽ các tam giác lên một tấm toan hình chữ nhật, cẩn thận để các đường biên của chúng không cắt nhau. Sau đó ông chọn một màu và tô các miền. Peer tô miền ngoài cùng (chính tấm toan) bằng sắc độ nhạt nhất của màu đã chọn. Rồi từng bước một, ông tô các miền nằm sâu hơn bên trong bằng sắc độ đậm hơn của cùng màu đó. Hình dưới đây là một bức trong loạt tranh "Hình khối màu xanh lá" của ông.

Một bức tranh "Hình khối màu xanh lá" của Peer.
Theo một nghĩa nào đó, quy trình này khá máy móc. Điều duy nhất Peer thấy khó là quyết định, sau khi đã vẽ xong các tam giác, ông sẽ cần bao nhiêu sắc độ khác nhau. Bạn hãy viết chương trình tính giúp ông.
Chương trình nhận vào một tập các tam giác và phải tính số sắc độ khác nhau cần dùng để tô các miền theo quy tắc trên.
Chương trình cũng phải phát hiện những lần hiếm hoi Peer vẽ nhầm, tức là vẽ các tam giác cắt nhau. Hai tam giác được coi là cắt nhau nếu các cạnh của tam giác này có ít nhất một điểm chung với các cạnh của tam giác kia. Khi đó tập tam giác không hợp lệ.
Dữ liệu vào
Dữ liệu gồm nhiều bộ test. Dòng đầu tiên của mỗi bộ test chứa một số nguyên không âm là số tam giác. dòng tiếp theo, mỗi dòng mô tả một tam giác theo định dạng x1 y1 x2 y2 x3 y3, trong đó là các số nguyên, là tọa độ các đỉnh của tam giác. Dữ liệu đảm bảo ba đỉnh của mỗi tam giác không thẳng hàng.
Sau bộ test cuối cùng là một dòng chứa duy nhất số .
Dữ liệu ra
Với mỗi bộ test, in số thứ tự bộ test (bắt đầu từ ) và số sắc độ cần dùng để tô các miền nếu bộ test hợp lệ, theo định dạng Case k: S shades (luôn viết shades, kể cả khi ). Nếu bộ test không hợp lệ (có hai tam giác cắt nhau), in Case k: ERROR. Xem định dạng trong ví dụ.
Ràng buộc
- .
- .
- Mỗi file có không quá bộ test và tổng các giá trị trong một file không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 8 8 3 8 4 7 4 14 13 -1 9 9 0 1 8 7 7 4 10 5 10 11 8 13 12 9 10 11 10 11 9 2 7 9 1 10 6 5 5 5 6 8 6 9 2 9 5 6 4 2 0 0 1 0 0 1 2 0 1 1 1 -1 -1 |
Case 1: 5 shades Case 2: ERROR |
Bộ 1 là bức tranh trong hình: các tam giác lồng nhau sâu nhất tầng, cộng với tấm toan là sắc độ. Ở bộ 2, đỉnh của tam giác thứ hai nằm trên cạnh từ đến của tam giác thứ nhất. |
| 0 1 0 0 4 0 0 3 3 0 0 0 6 6 3 0 7 0 13 6 10 -10 -10 30 6 -10 30 2 2 0 2 4 4 2 2 2 0 1 0 3 -1 |
Case 1: 1 shades Case 2: 2 shades Case 3: 3 shades Case 4: ERROR |
Bộ 1 không có tam giác nào, chỉ cần tô tấm toan. Bộ 3: hai tam giác đầu có cạnh đứng cùng nằm trên đường nhưng không chạm nhau, cả hai nằm trong tam giác thứ ba. Bộ 4: đỉnh của tam giác thứ hai nằm trên cạnh đứng của tam giác thứ nhất. |
Bình luận