Bẻ cong nhãn cầu
Đề bài
Mô tả
"Bẻ cong nhãn cầu" (eyeball benders) là một loại câu đố phổ biến, trong đó người đọc phải nhận ra một đồ vật quen thuộc chỉ dựa vào hình phóng to của một phần đồ vật đó. Ví dụ, một bức ảnh trông như một dãy nón màu xếp đều nhau có thể là hình chụp một hộp bút sáp màu mới vừa mở. Hình 1 là một ví dụ: câu đố ở bên trái, lời giải ở bên phải (một chiếc đĩa mềm).

Hình 1. Một câu đố "bẻ cong nhãn cầu" và hình lời giải (một chiếc đĩa mềm).
Bạn phải kiểm tra lời giải của một phiên bản đơn giản hoá của câu đố này. Bạn được cho một số cặp hình, mỗi hình là một tập các đoạn thẳng. Mọi đoạn thẳng đều nằm ngang hoặc thẳng đứng, và bao gồm cả hai đầu mút. Hình 2 là một ví dụ.
Bạn phải xác định xem mỗi cặp hình có hợp lệ không, tức là hình thứ nhất (hình câu đố) có phải là hình phóng to của một phần nào đó của hình thứ hai (hình lời giải) hay không. Các đoạn thẳng được coi là có độ dày bằng trong cả hai hình. Trong một cặp hợp lệ, ít nhất một đầu mút trong hình câu đố phải là đầu mút của một đoạn thẳng trong hình lời giải.

Hình 2. Hình bên trái là phần của hình bên phải nằm trong hình chữ nhật nét đứt, được phóng to lần.
Toạ độ mô tả vị trí và tỉ lệ tương đối bên trong một hình. Toạ độ của hai hình không nhất thiết có cùng gốc toạ độ hay cùng tỉ lệ. Hệ số phóng to của hình câu đố so với hình lời giải phải lớn hơn hoặc bằng . Với Hình 2, chương trình của bạn phải kết luận đây là một cặp câu đố/lời giải hợp lệ.
Nói chính xác: cặp hình hợp lệ khi và chỉ khi tồn tại một hình chữ nhật đóng (cạnh song song với các trục, trong toạ độ của hình lời giải), một hệ số và một phép tịnh tiến sao cho, khi lấy phần giao của từng đoạn thẳng trong hình lời giải với , rồi nhân toạ độ với và tịnh tiến, ta được đúng tập đoạn thẳng của hình câu đố (mỗi phần giao có độ dài dương ứng với đúng một đoạn của hình câu đố và ngược lại), đồng thời có ít nhất một đầu mút của hình câu đố ứng với một đầu mút của một đoạn trong hình lời giải. Không được xoay hay lật hình. Các đoạn thẳng không xuất hiện trong hình câu đố phải cách ít nhất ; nói riêng, nếu một đoạn của hình lời giải chạm tại đúng một điểm thì cách đặt đó không hợp lệ.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng hai số nguyên dương và (). là số đoạn thẳng của hình câu đố, là số đoạn thẳng của hình lời giải được đề xuất. Tiếp theo là cặp điểm: cặp đầu tiên là hai đầu mút của các đoạn thẳng trong hình câu đố, cặp còn lại là hai đầu mút của các đoạn thẳng trong hình lời giải. Mỗi điểm gồm hai toạ độ và thoả mãn , có không quá ba chữ số sau dấu thập phân. Mọi giá trị được phân cách bởi khoảng trắng (dấu cách hoặc xuống dòng).
Trong cùng một hình, không có hai điểm phân biệt nào cách nhau ít hơn (theo tỉ lệ của hình đó) và mọi đoạn thẳng có độ dài ít nhất . Không có hai đoạn nằm ngang nào chồng lên nhau và không có hai đoạn thẳng đứng nào chồng lên nhau; tuy nhiên đoạn nằm ngang có thể cắt đoạn thẳng đứng, ở phần trong hoặc tại đầu mút của đoạn.
Sau bộ test cuối cùng là một dòng gồm hai số nguyên 0 0.
Dữ liệu ra
Với mỗi bộ test, in số thứ tự của bộ test () theo sau là valid puzzle nếu hình câu đố khớp với một vùng hình chữ nhật đóng của hình lời giải (chứa ít nhất một đầu mút), được phóng to với hệ số lớn hơn hoặc bằng và có thể được tịnh tiến. Nếu điều kiện khớp không thoả mãn, in impossible. Định dạng theo đúng ví dụ.
Ràng buộc
- ; , tối đa ba chữ số thập phân.
- Mỗi đoạn thẳng nằm ngang hoặc thẳng đứng, độ dài ít nhất .
- Trong cùng một hình, hai đầu mút phân biệt cách nhau ít nhất , và hai đoạn cùng nằm ngang (hoặc cùng thẳng đứng) không có điểm chung.
- Mỗi file có không quá bộ test.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 12 9 8 7.5 8 1.5 8 1.5 3.5 0 5 9 5 4 2 8 2 5 7 2 7 10 6 8 6 8 7 8 4 1 9 8 9 9 3 7 3 4 10 4 5 4 2 4 4 5 8 5 7 3 6 6 6 0 3 3 3 5 1 5 3 4 12 -50 -5 50 -5 0 10 0 -10 50 5 -50 5 -50 0 50 0 4 2 8 2 5 7 2 7 10 6 8 6 8 7 8 4 1 9 8 9 9 3 7 3 4 10 4 5 4 2 4 4 5 8 5 7 3 6 6 6 0 3 3 3 5 1 5 3 0 0 |
Case 1: valid puzzle Case 2: impossible |
Bộ 1 là Hình 2: hình câu đố là vùng , của hình lời giải phóng to lần; điểm ứng với đầu mút . Bộ 2: hình câu đố có ba đoạn nằm ngang cách đều nhau cùng bị một đoạn thẳng đứng cắt qua, hình lời giải không có chỗ nào như vậy. |
| 2 2 0 0 10 0 0 10 0 0 0 0 3 0 0 0 0 1 2 2 0 0 1 0 0 1 1 1 0 0 2 0 0 2 2 2 2 2 0 0 2 0 0 2 2 2 0 0 1 0 0 1 1 1 0 0 |
Case 1: valid puzzle Case 2: impossible Case 3: valid puzzle |
Bộ 1: chọn là hình vuông và ; đầu mút ứng với đầu mút chung của hai đoạn. Bộ 2: hình câu đố là hình lời giải thu nhỏ lần, hệ số nên không hợp lệ. Bộ 3: đổi vai hai hình của bộ 2, . |
Bình luận