trang chủ / đề bài / icpcwf11_b

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 x và theo y 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 x và theo y là các số nguyên khác 0 (có thể âm); tâm co giãn là gốc tọa độ (0,0).
  • Độ tịnh tiến theo x và theo y là các số nguyên.
  • Phép xoay được xác định bởi một điểm có tọa độ nguyên (x,y) nằm trên chu vi hình vuông cạnh 20 có tâm tại gốc tọa độ (nghĩa là −10≤x,y≤10 và giá trị tuyệt đối của x hoặc y, hoặc cả hai, bằng 10). Công cụ xoay bản vẽ quanh gốc tọa độ sao cho sau khi xoay, tia dương của trục x đi qua điểm (x,y).
  • 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 0.5 được làm tròn ra xa số 0).

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 xi, yi (1≤i≤6), 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ụ (x1,y1) có thể đã được biến thành bất kỳ điểm nào trong (x4,y4), (x5,y5), (x6,y6).

Sau bộ test cuối cùng là một dòng gồm sáu số 0.

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 solutions nế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 solutions nế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 solution nế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 i là số thứ tự bộ test bắt đầu từ 1.

Ràng buộc

  • −500≤xi,yi≤500 với 1≤i≤6.
  • 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 độ 1 và cùng được đưa tới tung độ 2: không xoay, tịnh tiến theo x thêm 1, và theo y có thể dùng hệ số co giãn 1 (tịnh tiến 1) hoặc 2 (tịnh tiến 0) hoặc nhiều hệ số khác; các phép này biến điểm (0,0) 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 180∘ rồi co giãn hệ số −1 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 y=5; hệ số co giãn theo y có thể là bất kỳ số nguyên khác 0 nào. Ở bộ 2 không có phép biến đổi hợp lệ nào.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0