Mớ hỗn độn affine
Đề bài
Mô tả
Tuần trước, Tess L. Ation gặp một rắc rối nhỏ khi trình diễn bản beta của phần mềm vẽ mới. Trên màn hình là một bản thiết kế mẫu rất đẹp minh họa mọi tính năng của chương trình, cô đã mất hàng giờ để tạo ra nó. Cô vừa hoàn thiện những nét cuối cùng thì một nhóm nhà đầu tư tiềm năng bước vào phòng để xem buổi trình diễn.
Buổi trình diễn diễn ra suôn sẻ. Gần cuối, Tess bấm một nút trên bảng điều khiển và nói với khán giả: "Đây là chức năng 'bắt dính vào lưới'. Nó buộc các điểm điều khiển, chẳng hạn các đỉnh, nhảy tới điểm lưới gần nhất. Để tôi cho các vị xem", rồi cô đặt ba chấm đỏ lên màn hình. Mỗi chấm xuất hiện tại điểm lưới gần nhất với chỗ cô bấm. ("May là mọi điểm điều khiển trong bản thiết kế mẫu đều đã có tọa độ nguyên. Nhưng mình phải nhớ xóa ba chấm đỏ này trước khi lưu bản vẽ", cô tự nhủ.) "Bây giờ tôi sang phòng bên để các vị tự trao đổi và xem kỹ màn hình, nhưng xin đừng chạm vào thứ gì, vì tôi chưa lưu tệp."
Vài phút sau, cả nhóm sang gặp Tess. Một vị khách nói: "Mong cô không phiền, tôi muốn tự thử một chút. Đừng lo, tôi chỉ chỉnh thang tỉ lệ theo và theo một chút thôi." Người tiếp theo nói: "Xin lỗi nếu có vấn đề gì, nhưng tôi rất muốn cảm nhận tốc độ hiển thị nên đã nghịch công cụ tịnh tiến." Người thứ ba nói: "Tôi không cưỡng lại được một thử nghiệm nhỏ: tôi đã xoay hình để xem mọi đỉnh bắt dính vào điểm lưới gần nhất sau khi xoay."
Người dùng công cụ xoay nhớ rằng mình làm đầu tiên, còn hai người kia không nhớ ai làm trước. Cả ba chỉ nhớ vài chi tiết về các thay đổi:
- Hệ số co giãn theo và theo là các số nguyên khác (có thể âm); tâm co giãn là gốc tọa độ .
- Độ tịnh tiến theo và theo là các số nguyên.
- Phép xoay được xác định bởi một điểm có tọa độ nguyên nằm trên chu vi hình vuông cạnh có tâm tại gốc tọa độ (nghĩa là và giá trị tuyệt đối của hoặc , hoặc cả hai, bằng ). Công cụ xoay bản vẽ quanh gốc tọa độ sao cho sau khi xoay, tia dương của trục đi qua điểm .
- Việc bắt dính diễn ra sau phép xoay: mỗi tọa độ được làm tròn tới số nguyên gần nhất (tọa độ có phần thập phân đúng bằng được làm tròn ra xa số ).
Sau khi khách về, Tess nhìn bản thiết kế của mình: nó đã thay đổi hoàn toàn! Cô chưa cài đặt chức năng "hoàn tác" và cũng chưa lưu bản vẽ trước buổi trình diễn. Tuy nhiên ba chấm đỏ giống hệt nhau vẫn còn đó (tất nhiên đã bị biến đổi tới các điểm lưới nguyên khác), và Tess nhớ tọa độ nguyên ban đầu của chúng. Dĩ nhiên có thể ai đó đã thay đổi bản vẽ mà không nói với cô, nhưng cô có thể viết chương trình để xem có dựng lại được dãy thay đổi hay không. Bạn có làm được không?
Một phép biến đổi hợp lệ là tổ hợp gồm phép xoay (kèm bắt dính), rồi tịnh tiến rồi co giãn (hoặc xoay, rồi co giãn rồi tịnh tiến), thỏa các ràng buộc trên và biến tập ba chấm đỏ ban đầu thành tập ba vị trí cuối (chiếm đủ cả ba vị trí cuối).
Dữ liệu vào
Dữ liệu gồm nhiều bộ test. Mỗi bộ test gồm sáu cặp số nguyên , (), mỗi dòng ba cặp. Ba cặp đầu là ba vị trí ban đầu đôi một phân biệt của ba chấm đỏ. Ba cặp sau là ba vị trí cuối đôi một phân biệt của ba chấm. Thứ tự các cặp trong mỗi nhóm ba không có ý nghĩa: ví dụ có thể đã được biến thành bất kỳ điểm nào trong , , .
Sau bộ test cuối cùng là một dòng gồm sáu số .
Dữ liệu ra
Với mỗi bộ test, in số thứ tự của bộ test theo sau là một trong ba thông báo:
equivalent solutionsnếu có ít nhất một phép biến đổi hợp lệ và mọi phép biến đổi hợp lệ đều có cùng tác dụng lên toàn bộ bản vẽ (bất kể bản vẽ trông như thế nào);inconsistent solutionsnếu có nhiều phép biến đổi hợp lệ nhưng nói chung chúng không biến toàn bộ bản vẽ theo cùng một cách (có bản vẽ bị hai phép biến đổi hợp lệ biến thành hai kết quả khác nhau);no solutionnếu không xảy ra hai trường hợp trên.
Định dạng theo đúng ví dụ: Case i: rồi đến thông báo, với là số thứ tự bộ test bắt đầu từ .
Ràng buộc
- với .
- Ba điểm ban đầu đôi một phân biệt, ba điểm cuối đôi một phân biệt.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 0 4 0 1 4 -2 -4 -1 3 3 -4 0 1 1 1 2 1 1 2 2 2 3 2 1 0 2 0 3 0 3 3 1 1 2 2 1 0 2 0 3 0 3 2 1 1 2 2 2 3 0 6 1 2 2 3 0 6 1 2 0 0 0 0 0 0 |
Case 1: equivalent solutions Case 2: inconsistent solutions Case 3: no solution Case 4: inconsistent solutions Case 5: equivalent solutions |
Ở bộ 2, cả ba điểm có cùng tung độ và cùng được đưa tới tung độ : không xoay, tịnh tiến theo thêm , và theo có thể dùng hệ số co giãn (tịnh tiến ) hoặc (tịnh tiến ) hoặc nhiều hệ số khác; các phép này biến điểm thành những điểm khác nhau. Ở bộ 5, các điểm giữ nguyên vị trí: không xoay và không đổi gì, hoặc xoay rồi co giãn hệ số theo cả hai trục; hai cách này có cùng tác dụng lên mọi điểm. |
| 0 0 1 0 2 0 5 5 6 5 7 5 1 1 2 3 4 4 2 2 4 6 8 9 0 0 0 0 0 0 |
Case 1: inconsistent solutions Case 2: no solution |
Ở bộ 1, ba điểm nằm trên trục hoành được đưa lên đường thẳng ; hệ số co giãn theo có thể là bất kỳ số nguyên khác nào. Ở bộ 2 không có phép biến đổi hợp lệ nào. |
Bình luận