trang chủ / đề bài / icpcwf07_d

Mạch Jacquard

Đề bài

Mô tả

Nhà điêu khắc lập dị Albrecht Caravaggio Mondrian lấy cảm hứng từ lịch sử máy tính để tạo ra những tác phẩm mà ông gọi là "mạch Jacquard". Mỗi tác phẩm gồm một loạt bảng mạch hình đa giác (định nghĩa bên dưới), tất cả có cùng hình dạng nhưng khác tỉ lệ, được nối với nhau bằng dây kim loại hoặc dây sợi thành một cấu trúc ba chiều nhiều tầng. Hình 1 dưới đây là một ví dụ với hai tầng có dạng ngũ giác.

Hình 1

A.C.M. (bạn bè gọi ông như vậy) dựa nghệ thuật của mình trên các tấm thẻ đục lỗ của máy dệt Jacquard (về sau được Charles Babbage dùng cho máy giải tích của ông) và trên cách bố trí theo lưới đều thường dùng khi ghép nối mạch điện (chẳng hạn Pin Grid Array).

Các bảng mạch trong tác phẩm có hình đa giác nguyên. Đa giác nguyên là một chu trình khép kín, không tự cắt, gồm các đoạn thẳng nối những điểm có toạ độ nguyên, trong đó không có hai đoạn liên tiếp nào song song. Với mỗi đa giác nguyên P, tồn tại một đa giác nguyên nhỏ nhất có cùng hình dạng và cùng hướng với P, gọi là gốc. Các đa giác nguyên cùng hình dạng và cùng hướng với P nhưng nhỏ hơn P gọi là các tiền thân của P, các đa giác lớn hơn P gọi là các hậu duệ của P (xem Hình 2).

Hình 2: đa giác mẫu P (nét liền), tiền thân liền trước của P, hậu duệ liền sau của P và gốc (nét đứt).

Để làm một tác phẩm, A.C.M. chọn ngẫu nhiên N điểm nguyên rồi vẽ một hình bằng cách nối các điểm này theo thứ tự. (Lưu ý rằng không phải N điểm nào cũng là đỉnh của đa giác nguyên, chẳng hạn khi có từ ba điểm liên tiếp trở lên thẳng hàng.) Gọi P là đa giác nguyên xác định bởi hình vẽ đó. Ông tìm gốc của P, chọn số tầng M muốn dùng, rồi làm M bảng mạch đầu tiên của dãy (tức là gốc và M−1 hậu duệ đầu tiên của gốc). Mỗi điểm nguyên nằm thực sự bên trong biên của một trong các đa giác này là một lỗ, nơi các sợi dây gặp nhau.

Phần khó khi làm tác phẩm là buộc tất cả các sợi dây gặp nhau tại cùng một lỗ. Hơn nữa, một số tác phẩm thu nhỏ nổi tiếng của A.C.M., được làm bằng kỹ thuật nano, có tới hàng trăm nghìn tầng. Mondrian muốn biết, với một hình đa giác và số tầng cho trước, tác phẩm hoàn chỉnh có bao nhiêu lỗ. Hãy viết chương trình giúp ông. (Ví dụ, tác phẩm ở Hình 1 có 15 lỗ.) Coi lỗ có đường kính bằng 0.

Dữ liệu vào

Dữ liệu gồm một hoặc nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên dương N và M: N là số điểm nguyên Mondrian đã chọn và M là số tầng của tác phẩm hoàn chỉnh. Mỗi dòng trong N dòng tiếp theo chứa hai số nguyên x,y là toạ độ một điểm. Các điểm được liệt kê theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ.

Sau bộ test cuối cùng là một dòng chứa hai số 0.

Dữ liệu ra

Với mỗi bộ test, in một dòng gồm số thứ tự bộ test (bắt đầu từ 1) và số lỗ của tác phẩm M tầng bắt đầu từ gốc của hình đã cho, theo đúng định dạng ở ví dụ. Đảm bảo giá trị này không vượt quá giá trị lớn nhất của kiểu số nguyên có dấu 64 bit.

Ràng buộc

  • 3≤N≤1000, 1≤M≤106, |x|,|y|≤106.
  • Các điểm của một bộ test đôi một phân biệt; nối chúng theo thứ tự (và nối điểm cuối với điểm đầu) được một đường gấp khúc khép kín không tự cắt, có diện tích dương. Ba điểm liên tiếp có thể thẳng hàng (khi đó điểm ở giữa nằm trên đoạn nối hai điểm kia).
  • Mỗi file có không quá 1000 bộ test và tổng N không quá 200000.

Ví dụ

Input Output Giải thích
5 2
0 0
8 0
12 4
8 8
0 8
3 2
-1 -1
3 1
5 -1
0 0
Case 1: 15
Case 2: 2
Bộ 1 là Hình 2: gốc có các đỉnh (0,0),(2,0),(3,1),(2,2),(0,2) (sai khác một phép tịnh tiến), tầng 1 có 2 lỗ, tầng 2 có 13 lỗ. Bộ 2: gốc là tam giác (0,0),(2,1),(3,0), không có lỗ; tầng 2 có 2 lỗ.
6 3
1 0
0 0
0 4
2 4
4 2
4 0
3 4
0 0
1 0
0 1
0 0
Case 1: 31
Case 2: 4
Bộ 1: điểm (1,0) nằm giữa cạnh từ (4,0) đến (0,0) nên không phải đỉnh. Gốc có các đỉnh (0,0),(0,2),(1,2),(2,1),(2,0); ba tầng có 1+8+22=31 lỗ. Bộ 2: tam giác vuông đơn vị là gốc của chính nó, bốn tầng có 0+0+1+3=4 lỗ.

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