1. Google Code Jam 2018 - Fence Construction
Fence Construction
Bạn là nhân viên của Công ty Xây dựng Hàng rào và được giao xây dựng \(F\) hàng rào. Mỗi hàng rào chạy theo một đường thẳng từ điểm này đến điểm khác. Nói chính xác hơn, mỗi hàng rào là một đoạn thẳng nối hai điểm phân biệt trong mặt phẳng hai chiều. Các hàng rào không giao nhau, ngoại trừ trường hợp có thể gặp nhau tại đầu mút. Toàn bộ các hàng rào liên thông: với mọi cặp hàng rào \(f\) và \(g\), tồn tại một dãy \(f=f_1,f_2,\ldots,f_k=g\) sao cho \(f_i\) có chung một đầu mút với \(f_{i+1}\).
Khi bạn bắt đầu công việc, chưa có hàng rào nào được xây. Việc thi công dùng một máy in 3D đặc biệt có khả năng "bắn" hàng rào. Chỉ có một thiết bị như vậy, nên các hàng rào được xây lần lượt từng chiếc. Máy in đủ nhỏ để có thể coi nó là một điểm trên mặt phẳng.
Để xây hàng rào \(f\), trước tiên bạn phải đặt máy in tại một điểm \(p\) trên mặt phẳng sao cho máy nhìn thấy toàn bộ \(f\) mà không bị các hàng rào đã xây trước đó che khuất. Nói chính xác hơn, \(p\) phải thỏa mãn:
- \(p\) không nằm trên \(f\), kể cả tại đầu mút;
- với mọi điểm \(q\) nằm trên \(f\) nhưng không phải đầu mút của \(f\), đoạn thẳng nối \(p\) với \(q\) không giao bất kỳ hàng rào nào đã xây.
Để đưa máy in tới vị trí cần thiết, bạn có thể di chuyển nó từ vị trí hiện tại theo một đường liên tục, không nhất thiết là đường thẳng, miễn là đường đi không giao bất kỳ hàng rào nào đã xây, kể cả tại đầu mút. Bạn được tự do chọn vị trí đặt máy trước khi xây hàng rào đầu tiên và sau khi xây hàng rào cuối cùng.
Quy trình này có nghĩa là bạn không nhất thiết có thể xây các hàng rào theo mọi thứ tự. Chẳng hạn, một thứ tự nào đó có thể nhốt máy in lại và khiến bạn không thể đưa nó tới vị trí cần thiết.
Giám đốc đã phác thảo một thứ tự tương đối cho \(K\) trong số các hàng rào (chưa hàng rào nào được xây), nhưng không suy nghĩ kỹ về tính khả thi. Để tránh làm giám đốc tức giận, bạn phải giữ thứ tự này, đồng thời chèn \(F-K\) hàng rào còn lại vào bất kỳ vị trí nào để hoàn thiện thứ tự.
Với các hạn chế trên, hãy tìm một thứ tự xây hàng rào. Đề bài bảo đảm có ít nhất một thứ tự hợp lệ.
Dữ liệu vào
Dòng đầu tiên chứa số lượng bộ test \(T\). Sau đó là \(T\) bộ test.
Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên \(F\) và \(K\): tổng số hàng rào và số hàng rào trong thứ tự chưa hoàn chỉnh của giám đốc. Tiếp theo là \(F\) dòng; dòng thứ \(i\) trong số đó (đánh số từ 1) chứa bốn số nguyên \(A_i\), \(B_i\), \(C_i\) và \(D_i\), cho biết hàng rào thứ \(i\) là đoạn thẳng từ \((A_i,B_i)\) đến \((C_i,D_i)\). \(K\) hàng rào đầu tiên được cho trong input chính là \(K\) hàng rào trong thứ tự của giám đốc.
Dữ liệu ra
Với mỗi bộ test, in một dòng có dạng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là một thứ tự gồm các số nguyên từ 1 đến \(F\), phân tách bằng dấu cách, biểu diễn một thứ tự hợp lệ để xây các hàng rào.
Ràng buộc
- \(1 \le T \le 100\).
- \(4 \le F \le 300\).
- \(-10^5 \le A_i \le 10^5\) với mọi \(i\).
- \(-10^5 \le B_i \le 10^5\) với mọi \(i\).
- \(-10^5 \le C_i \le 10^5\) với mọi \(i\).
- \(-10^5 \le D_i \le 10^5\) với mọi \(i\).
- \((A_i,B_i) \ne (C_i,D_i)\) với mọi \(i\).
- Nếu \(p\) là một điểm không phải đầu mút trên một hàng rào thì \(p\) không nằm trên bất kỳ hàng rào nào khác.
- Các hàng rào đã cho liên thông theo định nghĩa trong đề bài.
- Tồn tại ít nhất một thứ tự hàng rào thỏa mãn mọi hạn chế thi công trong đề bài.
Phân nhóm
- Test Set 1 (Visible): \(1 \le K \le 2\).
- Test Set 2 (Hidden): \(1 \le K < F\).
Điểm các phân nhóm
Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 12/35 | 34,29% |
| Test Set 2 | 23/35 | 65,71% |
Ví dụ
Ví dụ 1
Input
3
6 2
0 0 7 7
15 -2 10 0
0 0 0 10
0 0 10 0
0 10 10 10
10 0 10 10
6 1
0 0 0 10
0 0 10 0
0 10 10 10
10 0 10 10
0 0 7 7
15 -2 10 0
11 4
-10 0 10 0
-10 0 0 10
10 0 0 10
0 2 0 5
0 2 10 0
10 0 0 5
15 3 18 3
15 3 15 9
18 3 15 9
15 3 16 5
0 10 15 3Output
Case #1: 1 2 3 4 5 6
Case #2: 5 6 1 2 3 4
Case #3: 11 10 7 8 9 1 2 3 6 5 4Giải thích
Output mẫu chỉ đưa ra một trong các thứ tự hợp lệ; phần giải thích đầy đủ nằm bên dưới.
Test mẫu cuối cùng sẽ không xuất hiện trong Test Set 1.
Trong Test mẫu #1, có thể xây các hàng rào theo đúng thứ tự được cho: 1, 2, 3, 4, 5, 6. Lưu ý rằng theo danh sách của giám đốc, hàng rào 1 phải xuất hiện trước hàng rào 2.
Trong Test mẫu #2, không thể xây các hàng rào theo thứ tự được cho! Một thứ tự khả dĩ là: 5, 6, 1, 2, 3, 4. Lưu ý rằng khi danh sách của giám đốc chỉ chứa một hàng rào, điều kiện về thứ tự tương đối luôn hiển nhiên được thỏa mãn.
Trong Test mẫu #3, có thể xây các hàng rào theo thứ tự: 11, 10, 7, 8, 9, 1, 2, 3, 6, 5, 4. Lưu ý rằng các hàng rào 1, 2, 3 và 4 phải được xây theo đúng thứ tự tương đối đó.
Các hình sau minh họa một cách hợp lệ để xây các hàng rào trong Test mẫu #1.
Nguồn
Google Code Jam 2018, Vòng 3, bài Fence Construction.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
