trang chủ / đề bài / icpc23_reg_c

Bí ẩn vòng tròn trên cánh đồng

Đề bài

Mô tả

Keke, một người ngoài hành tinh tinh nghịch, đã hạ cánh xuống Trái Đất với một nhiệm vụ đặc biệt: tạo ra một vòng tròn nghệ thuật trên cánh đồng! Keke hình dung cánh đồng là một lưới lục giác vô hạn và muốn tô một số ô để tạo thành hình mẫu yêu thích của mình.

Keke dùng một hệ tọa độ lục giác để chia cánh đồng thành các ô lục giác, với tâm cánh đồng là ô (0,0). Trục x nằm ngang hướng sang phải; trục y hướng chéo lên phía trên bên trái. Các ô cùng tọa độ y nằm trên một hàng ngang, ô (x+1,y) nằm ngay bên phải ô (x,y), và hàng y+1 nằm phía trên hàng y, lệch sang trái nửa ô. Khi đó ô (x,y) có đúng 6 ô kề:

(x+1,y), (x−1,y), (x,y+1), (x,y−1), (x+1,y+1), (x−1,y−1).

Keke muốn tô một danh sách các ô, ô thứ i có tọa độ (xi,yi).

Phi thuyền của Keke có một khẩu súng tia đặc biệt, mỗi lần bắn tô một hình ngôi sao lên cánh đồng. Kích thước ngôi sao có thể từ 2 đến 666 (tính cả hai đầu). Ngôi sao kích thước r có tâm (x,y) gồm ô tâm và 6 tia, mỗi tia gồm r−1 ô liên tiếp đi thẳng từ tâm theo một trong 6 hướng ở trên, tức là các ô

(x,y) và (x+k·dx, y+k·dy) với 1≤k≤r−1, (dx,dy)∈{(1,0),(−1,0),(0,1),(0,−1),(1,1),(−1,−1)}.

Ví dụ, ngôi sao kích thước 2 tâm (0,0) gồm 7 ô (0,0), (1,0), (−1,0), (0,1), (0,−1), (1,1), (−1,−1); ngôi sao kích thước 3 tâm (6,3) gồm 13 ô: tâm (6,3) và các ô (7,3), (8,3), (5,3), (4,3), (6,4), (6,5), (6,2), (6,1), (7,4), (8,5), (5,2), (4,1).

Súng tia có một tính chất kỳ lạ: nếu một ô bị bắn trúng hai lần, ô đó trở về trạng thái ban đầu, tức là lớp sơn bị xóa đi. Nói cách khác, một ô được tô khi và chỉ khi nó bị bắn trúng một số lẻ lần. Keke có thể bắn nhiều nhất 666 lần. Keke đã mất vài tháng cố gắng tô hình mẫu yêu thích mà không thành công. Hãy giúp Keke!

Dữ liệu vào

Dòng đầu tiên chứa số nguyên t (1≤t≤6666), số bộ dữ liệu. Tiếp theo là t bộ dữ liệu, mỗi bộ có dạng:

  • Dòng đầu tiên chứa số nguyên n (0≤n≤66), số ô trong hình mẫu yêu thích của Keke.
  • n dòng tiếp theo, mỗi dòng chứa hai số nguyên xi và yi (0≤|xi|,|yi|≤6), tọa độ ô thứ i trong hình mẫu. Dữ liệu đảm bảo n ô đôi một khác nhau.

Dữ liệu đảm bảo tổng n trên mọi bộ dữ liệu không vượt quá 6666.

Dữ liệu ra

Với mỗi bộ dữ liệu, nếu không có cách nào, in ra NO. Ngược lại, in ra YES, tiếp theo là:

  • một dòng chứa số nguyên k (0≤k≤666), số lần bắn;
  • k dòng, dòng thứ j chứa ba số nguyên xj, yj và rj (0≤|xj|,|yj|≤666, 2≤rj≤666): lần bắn thứ j nhắm vào ô tâm (xj,yj) với ngôi sao kích thước rj.

Sau tất cả các lần bắn, tập ô được tô phải đúng bằng tập n ô của hình mẫu. Nếu có nhiều cách, in ra cách bất kỳ.

Ràng buộc

  • 1≤t≤6666, 0≤n≤66, 0≤|xi|,|yi|≤6, tổng n không vượt quá 6666.

Ví dụ

Input Output Giải thích
1
6
0 1
-1 0
-1 -1
2 1
2 0
1 -1
YES
2
0 0 2
1 0 2
Bắn ngôi sao kích thước 2 tâm (0,0) tô 7 ô quanh (0,0); bắn tiếp ngôi sao kích thước 2 tâm (1,0): bốn ô chung (0,0), (1,0), (1,1), (0,−1) bị xóa, còn lại đúng 6 ô của hình mẫu.
2
0
1
0 0
YES
0
YES
7
-1 -1 2
-1 0 2
0 -1 2
0 0 3
0 1 2
1 0 2
1 1 2
Hình mẫu rỗng không cần bắn lần nào. Bộ thứ hai: ngôi sao kích thước 3 tâm (0,0) cùng 6 ngôi sao kích thước 2 tâm tại 6 ô kề (0,0) chỉ để lại đúng ô (0,0).

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