Đề bài

Chalk đã tích cực chu du khắp thế giới cùng bạn bè và chụp ảnh tại tất cả những nơi thú vị nhất. Gần đây nhất, cậu đến châu Âu, nơi cậu tìm hiểu lịch sử của nghệ thuật gấp khăn ăn. Kể từ đó, Chalk đã sưu tầm rất nhiều loại khăn để luyện tập nghệ thuật gấp khăn.

Những chiếc khăn của Chalk có thể được biểu diễn bằng các đa giác đơn. Đa giác đơn là đa giác mà các cạnh không giao nhau, ngoại trừ hai cạnh kề nhau gặp nhau tại đỉnh chung. Mỗi đỉnh của đa giác thuộc đúng hai cạnh.

Trước khi gấp khăn, Chalk vẽ lên khăn một mẫu nếp gấp. Một mẫu nếp gấp là tập hợp gồm \(K-1\) đoạn thẳng được vẽ trên khăn. Mỗi đoạn thẳng nối hai điểm có tọa độ hữu tỉ trên biên của đa giác biểu diễn chiếc khăn và nằm hoàn toàn bên trong đa giác. Hai đoạn thẳng bất kỳ trong một mẫu nếp gấp không được chạm hoặc chồng lên nhau, ngoại trừ trường hợp chúng có chung đầu mút. Một mẫu nếp gấp gồm \(K-1\) đoạn thẳng chia chiếc khăn thành \(K\) miền đa giác. Hai điểm thuộc cùng một miền nếu tồn tại một đường liên tục nào đó (không nhất thiết là đường thẳng) nối chúng mà không giao với bất kỳ cạnh nào của đa giác hay bất kỳ đoạn thẳng nào trong mẫu nếp gấp — kể cả tại đầu mút.

Chalk chỉ quan tâm đến những mẫu nếp gấp gọn gàng. Một mẫu nếp gấp được gọi là gọn gàng nếu hai miền bất kỳ cùng kề với một đoạn nếp gấp \(F\) đều đối xứng qua \(F\). Điều này có nghĩa là khi gấp chiếc khăn theo đoạn thẳng đó, hai miền sẽ chồng khít hoàn toàn lên nhau.

Hình sau minh họa một mẫu nếp gấp gọn gàng với \(K=8\) miền.

Chalk đã gấp thành công bộ sưu tập khăn của mình bằng các mẫu nếp gấp gọn gàng. Tuy nhiên, trong bộ sưu tập vẫn có một số chiếc khăn mà cậu chưa tìm được mẫu nếp gấp gọn gàng. Với mỗi chiếc khăn như vậy, Chalk cần bạn giúp tìm một mẫu nếp gấp gọn gàng có \(K\) miền, hoặc xác định rằng không tồn tại mẫu nào như thế.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên \(N\) và \(K\): số đỉnh của đa giác biểu diễn chiếc khăn của Chalk và số miền cần chia chiếc khăn thành bằng một mẫu nếp gấp gọn gàng gồm \(K-1\) đoạn thẳng.

Đa giác biểu diễn chiếc khăn được cho dưới dạng danh sách \(N\) đỉnh theo thứ tự gặp được khi đi dọc chu vi đa giác theo chiều kim đồng hồ; đỉnh đầu tiên được chọn tùy ý. \(N\) dòng tiếp theo biểu diễn danh sách đó. Dòng thứ \(i\) trong số này chứa hai số nguyên \(X_i\) và \(Y_i\), cho biết điểm thứ \(i\) nằm tại tọa độ \((X_i, Y_i)\) trong mặt phẳng hai chiều.

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à POSSIBLE nếu có thể tạo một mẫu nếp gấp gọn gàng với \(K\) miền và là IMPOSSIBLE nếu không thể.

Nếu có thể tạo một mẫu nếp gấp gọn gàng với \(K\) miền, hãy in thêm \(K-1\) dòng liệt kê các đoạn thẳng của một mẫu nếp gấp gọn gàng với \(K\) miền, theo thứ tự bất kỳ. Mỗi dòng phải biểu diễn một đoạn thẳng khác nhau dưới dạng A_x A_y B_x B_y, trong đó \((A_x,A_y)\) và \((B_x,B_y)\) là hai đầu mút của đoạn thẳng, theo thứ tự bất kỳ. Mỗi giá trị trong \(A_x,A_y,B_x,B_y\) phải có dạng N/D, với N và D là các số nguyên dương (không có chữ số \(0\) thừa ở đầu), không có thừa số nguyên tố chung và biểu diễn số hữu tỉ \(N/D\). Không được có khoảng trắng giữa N và /, cũng như giữa / và D.

Ràng buộc

• \(1 \le T \le 100\).
• \(3 \le N \le 200\).
• \(1 \le X_i \le 1000\) với mọi \(i\).
• \(1 \le Y_i \le 1000\) với mọi \(i\).
• \(N\) điểm được cho theo thứ tự chiều kim đồng hồ.
• Không có hai cạnh kề nhau nào của đa giác thẳng hàng.
• Đa giác là một đa giác đơn có diện tích dương nghiêm ngặt.
• Hai cạnh bất kỳ không giao nhau, ngoại trừ hai cạnh kề nhau tại đầu mút chung của chúng.

Phân nhóm

Test Set 1 (Hiển thị): \(K=2\).

Test Set 2 (Ẩn): \(2 \le K \le 10\).

Đ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.

Ví dụ

4
4 2
1 1
1 2
2 2
2 1
3 2
1 1
1 2
2 1
8 2
1 3
3 5
5 5
4 4
7 3
5 1
4 2
3 1
8 2
1 3
3 5
4 4
5 5
7 3
5 1
4 2
3 1

Case #1: POSSIBLE
1/1 2/1 2/1 1/1
Case #2: POSSIBLE
1/1 1/1 3/2 3/2
Case #3: IMPOSSIBLE
Case #4: POSSIBLE
1/1 3/1 7/1 3/1

1
10 8
4 1
3 1
2 2
2 3
1 3
1 4
2 4
3 3
3 2
4 2

Case #1: POSSIBLE
3/1 1/1 4/1 2/1
3/1 1/1 3/1 2/1
2/1 2/1 3/1 2/1
2/1 2/1 3/1 3/1
2/1 3/1 3/1 3/1
2/1 3/1 2/1 4/1
1/1 3/1 2/1 4/1

Nguồn

Google Code Jam 2019, Vòng 3, bài Napkin Folding.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.