Thanh chống và lò xo
Đề bài
Mô tả
Thanh chống (strut) và lò xo (spring) là các cơ chế quyết định cách các cửa sổ hình chữ nhật trên màn hình thay đổi kích thước hoặc vị trí khi cửa sổ bao quanh chúng thay đổi kích thước. Mỗi cửa sổ chiếm một vùng hình chữ nhật trên màn hình, và nó có thể bao các cửa sổ khác, tạo thành một cây phân cấp các cửa sổ. Khi cửa sổ ngoài cùng thay đổi kích thước, mỗi cửa sổ nằm ngay bên trong nó có thể thay đổi vị trí hoặc kích thước (tùy theo cách đặt thanh chống và lò xo); các thay đổi này lại có thể ảnh hưởng tới vị trí và/hoặc kích thước của các cửa sổ mà chúng bao.
Về mặt khái niệm, thanh chống là một thanh có độ dài cố định, đặt giữa hai cạnh ngang hoặc hai cạnh dọc của một cửa sổ, hoặc giữa một cạnh của cửa sổ và cạnh tương ứng của cửa sổ bao ngay bên ngoài nó. Khi thanh chống nối hai cạnh dọc hoặc hai cạnh ngang của một cửa sổ thì chiều rộng hoặc chiều cao của cửa sổ đó cố định. Tương tự, khi thanh chống nối một cạnh của cửa sổ với cạnh tương ứng của cửa sổ bao ngay bên ngoài thì khoảng cách giữa hai cạnh đó cố định. Ngược lại, lò xo có thể bị nén hoặc kéo giãn, và có thể được dùng thay cho thanh chống.
Mỗi cửa sổ, trừ cửa sổ ngoài cùng, có sáu thanh chống hoặc lò xo gắn với nó. Một cái nối hai cạnh dọc của cửa sổ, một cái nối hai cạnh ngang của cửa sổ. Bốn cái còn lại, mỗi cái nối một cạnh của cửa sổ với cạnh tương ứng của cửa sổ bao nó. Tổng độ dài của ba thanh chống/lò xo theo phương dọc bằng chiều cao của cửa sổ bao; tương tự, tổng độ dài của ba thanh chống/lò xo theo phương ngang bằng chiều rộng của cửa sổ bao. Khi chiều rộng của cửa sổ bao thay đổi, mọi lò xo theo phương ngang gắn với cửa sổ đang xét bị kéo giãn hoặc nén theo cùng một tỉ lệ, sao cho tổng độ dài mới của các thanh chống và lò xo bằng chiều rộng mới. Điều tương tự xảy ra khi chiều cao của cửa sổ bao thay đổi. Nếu cả ba thành phần theo phương dọc đều là thanh chống thì thanh chống phía trên được coi như được thay bằng một lò xo; nếu cả ba thành phần theo phương ngang đều là thanh chống thì thanh chống bên phải được coi như được thay bằng một lò xo.
Hãy viết chương trình nhận kích thước và vị trí ban đầu của một tập các cửa sổ (có một cửa sổ chắc chắn bao tất cả các cửa sổ còn lại), cách đặt các thanh chống và lò xo, cùng các yêu cầu thay đổi kích thước cửa sổ ngoài cùng, rồi xác định kích thước và vị trí mới của từng cửa sổ sau mỗi yêu cầu.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test, mỗi bộ test là một tập cửa sổ. Mỗi bộ test bắt đầu bằng một dòng chứa bốn số nguyên , , và : là số cửa sổ (không tính cửa sổ ngoài cùng bao tất cả các cửa sổ khác), là số yêu cầu thay đổi kích thước cửa sổ ngoài cùng, và là chiều rộng và chiều cao ban đầu của cửa sổ ngoài cùng.
Mỗi dòng trong dòng tiếp theo chứa số nguyên không âm mô tả một cửa sổ. Hai số đầu là độ dời ban đầu theo và theo của góc trên bên trái cửa sổ so với góc trên bên trái của cửa sổ ngoài cùng ( tăng sang phải, tăng xuống dưới). Hai số tiếp theo là chiều rộng và chiều cao ban đầu của cửa sổ. Mỗi số trong sáu số cuối là (thanh chống) hoặc (lò xo). Hai số đầu trong sáu số này cho biết thứ nối hai cạnh dọc (tức chiều rộng) và thứ nối hai cạnh ngang (tức chiều cao) của cửa sổ là thanh chống hay lò xo; bốn số sau cho biết thứ nối cạnh trên, cạnh dưới, cạnh trái và cạnh phải của cửa sổ với cạnh tương ứng của cửa sổ bao ngay bên ngoài nó là thanh chống hay lò xo.
Mỗi dòng trong dòng cuối của bộ test cho chiều rộng và chiều cao mới của cửa sổ ngoài cùng: một thao tác thay đổi kích thước. Với mỗi thao tác, chương trình phải xác định kích thước và vị trí của từng cửa sổ trong cửa sổ bên trong.
Bộ test cuối cùng được theo sau bởi một dòng chứa bốn số .
Dữ liệu ra
Với mỗi thao tác thay đổi kích thước trong một bộ test, in số thứ tự bộ test (bắt đầu từ ) và số thứ tự thao tác () trên một dòng riêng. Sau đó, trên mỗi dòng trong dòng tiếp theo, in số hiệu cửa sổ, vị trí ( và ) và kích thước (chiều rộng và chiều cao) của từng cửa sổ bên trong sau khi cửa sổ ngoài cùng được đổi kích thước. Các cửa sổ trong một bộ test được đánh số liên tiếp () theo thứ tự xuất hiện trong dữ liệu vào, và phải được in theo thứ tự đó. Vị trí được tính so với góc trên bên trái của cửa sổ ngoài cùng. Làm theo đúng định dạng trong ví dụ:
Case 1, resize operation 1:
Window 1, x = 10, y = 60, width = 50, height = 10
Ràng buộc
- , .
- Chiều rộng và chiều cao của cửa sổ ngoài cùng (ban đầu và sau mọi thao tác) là số nguyên từ đến .
- Hai cửa sổ bất kỳ hoặc có một cái nằm hẳn bên trong cái kia, hoặc không có điểm chung; biên của các cửa sổ khác nhau không chạm nhau. Cửa sổ bao ngay bên ngoài một cửa sổ là cửa sổ nhỏ nhất chứa nó (hoặc cửa sổ ngoài cùng).
- Ban đầu và sau mọi thao tác thay đổi kích thước, mọi thanh chống và lò xo đều có độ dài nguyên dương, và biên của các cửa sổ khác nhau không chạm nhau. Việc đổi kích thước không bao giờ làm một cửa sổ "nhảy" vào bên trong một cửa sổ khác.
- Mỗi file có không quá bộ test và tổng trên các bộ test không quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 1 50 100 10 10 30 10 1 0 0 0 0 0 70 150 2 1 50 100 10 10 30 10 1 0 0 0 0 0 10 80 20 10 1 1 0 0 0 0 70 150 1 2 60 60 10 10 20 30 1 0 1 1 1 1 90 90 120 120 0 0 0 0 |
Case 1, resize operation 1: Window 1, x = 10, y = 60, width = 50, height = 10 Case 2, resize operation 1: Window 1, x = 10, y = 60, width = 50, height = 10 Window 2, x = 10, y = 80, width = 40, height = 60 Case 3, resize operation 1: Window 1, x = 15, y = 20, width = 30, height = 30 Case 3, resize operation 2: Window 1, x = 20, y = 30, width = 40, height = 30 |
Bộ 1: theo phương ngang chỉ chiều rộng là lò xo nên nó giãn từ thành ; theo phương dọc cả ba đều là thanh chống nên thanh chống phía trên giãn từ thành . Bộ 3: theo phương ngang ba lò xo giãn cùng tỉ lệ thành (rồi ); theo phương dọc hai lò xo và chia phần thành và . |
| 3 2 100 60 40 20 20 20 1 1 1 1 1 1 10 10 80 40 1 0 0 0 0 0 30 42 40 6 0 0 0 0 0 0 140 90 84 55 0 0 0 0 |
Case 1, resize operation 1: Window 1, x = 55, y = 50, width = 30, height = 20 Window 2, x = 10, y = 40, width = 120, height = 40 Window 3, x = 30, y = 72, width = 40, height = 6 Case 1, resize operation 2: Window 1, x = 34, y = 15, width = 16, height = 20 Window 2, x = 10, y = 5, width = 64, height = 40 Window 3, x = 30, y = 37, width = 40, height = 6 |
Cửa sổ 1 và 3 nằm trong cửa sổ 2. Thao tác 1: cửa sổ 2 rộng , thanh chống trên giãn thành ; trong cửa sổ 2 (rộng ), ba lò xo ngang của cửa sổ 1 thành ; chiều cao cửa sổ 2 là thanh chống nên theo phương dọc cửa sổ 1, 3 chỉ dời theo cửa sổ 2; cửa sổ 3 toàn thanh chống nên thanh chống bên phải giãn thành . Thao tác 2 thu nhỏ: cửa sổ 2 rộng , các lò xo của cửa sổ 1 thành . |
Bình luận