Quy cách nộp và chấm cục bộ

Đây là bài chỉ nộp kết quả (OUTPUT). Tải contestant-input.zip, rồi nộp một
ZIP chứa tests/01.out, tests/02.out, tests/03.out, tests/04.out và
tests/05.out, lần lượt ứng với n = 6, 11, 17, 22, 90. Mỗi tệp chứa đúng
n dòng tọa độ; không ghi n, bán kính hoặc điểm số vào kết quả.

Bộ chấm dùng các bố trí sinh xác định trong reference-output.zip làm tập
tham chiếu cục bộ. Đây không phải tập bài nộp lịch sử; tập tham chiếu tốt
nhất của kỳ thi lịch sử không còn được cung cấp. Vì vậy, điểm cục bộ không tái
tạo điểm lịch sử. Với bán kính d, bán kính mốc d0 và bán kính tham chiếu
d1, tỷ lệ điểm là min(1, (d-d0)/(d1-d0)) nếu d>d0, ngược lại bằng 0.
Kết quả không hợp lệ được 0. Mỗi bộ nhân tỷ lệ này với 20 đúng một lần.

Các ví dụ n=3 và n=8 bên dưới chỉ minh họa hình học, không phải bộ chấm.
Tên tệp và quy tắc chấm cục bộ ở trên thay thế quy cách lịch sử bên dưới.

Bạn làm việc tại một nhà máy bán dẫn, nơi các tấm silic được gia công thành nguyên liệu để sản xuất chip. Thiết bị gia công có thể điều chỉnh vị trí với độ chính xác \(10\) nanomét, tức \(1/100\,000\,000\) mét.

Một khách hàng yêu cầu cắt \(n\) đĩa tròn bằng nhau từ một tấm silic hình vuông có cạnh dài \(1\) mét. Các đĩa phải nằm hoàn toàn trong tấm vuông và không được chồng lấn phần bên trong; chúng có thể tiếp xúc nhau hoặc tiếp xúc với cạnh tấm vuông. Hãy bố trí các đĩa để bán kính chung của chúng lớn nhất có thể.

Đây là bài chỉ nộp kết quả (Output Only), được chấm bằng cách so sánh tương đối giữa các kết quả đã nộp. Bạn chỉ nộp các tệp kết quả, không nộp chương trình. Có thể tạo kết quả bằng chương trình, chỉnh sửa bằng trình soạn thảo văn bản hoặc dùng bất kỳ cách nào khác.

Dữ liệu vào

Có năm bộ dữ liệu cố định, được cho trực tiếp như sau:

• Bộ \(1\): \(n=6\).
• Bộ \(2\): \(n=11\).
• Bộ \(3\): \(n=17\).
• Bộ \(4\): \(n=22\).
• Bộ \(5\): \(n=90\).

Dữ liệu ra

Với bộ dữ liệu số \(k\) (\(1\le k\le5\)), nộp tệp packing-outk.txt, thay k bằng số bộ dữ liệu tương ứng. Cụ thể, năm tên tệp là packing-out1.txt, packing-out2.txt, packing-out3.txt, packing-out4.txt và packing-out5.txt.

Mỗi tệp gồm đúng \(n\) dòng. Dòng thứ \(i\) chứa hai số nguyên \(x_i,y_i\), phân cách bằng dấu cách, mô tả tâm của đĩa thứ \(i\). Tâm cách cạnh trái của tấm vuông \(x_i\times10\) nanomét và cách cạnh trên \(y_i\times10\) nanomét. Vì vậy, tọa độ \(y\) tăng theo chiều từ trên xuống dưới.

Không ghi bán kính vào tệp kết quả: thiết bị tự tính bán kính chung lớn nhất có thể của các đĩa từ các tâm đã cho.

Ràng buộc

• Mỗi tệp phải chứa đúng số tâm của bộ dữ liệu tương ứng.
• \(x_i,y_i\) là các số nguyên thỏa mãn \(0\le x_i,y_i\le100\,000\,000\) (\(1\le i\le n\)).
• Cần tránh tràn số khi tính toán: \(2^{32}=4\,294\,967\,296\). Nếu dùng C/C++ để tạo kết quả, có thể dùng double hoặc long long int khi cần.

Phân nhóm

• Bộ \(1\): tối đa \(20\) điểm, \(n=6\); nộp packing-out1.txt.
• Bộ \(2\): tối đa \(20\) điểm, \(n=11\); nộp packing-out2.txt.
• Bộ \(3\): tối đa \(20\) điểm, \(n=17\); nộp packing-out3.txt.
• Bộ \(4\): tối đa \(20\) điểm, \(n=22\); nộp packing-out4.txt.
• Bộ \(5\): tối đa \(20\) điểm, \(n=90\); nộp packing-out5.txt.

Bán kính mốc dùng để chấm được xác định như sau. Lấy số nguyên \(m\) thỏa mãn \((m-1)^2<n\le m^2\). Chia tấm vuông thành \(m\times m\) ô vuông bằng nhau, chọn \(n\) ô và lấy đường tròn nội tiếp mỗi ô. Bán kính của cách bố trí mốc này là \(d_0=1/(2m)\) mét. Cách bố trí mốc không nhất thiết là tối ưu.

Mỗi bộ dữ liệu được chấm độc lập. Nếu không nộp tệp, tệp không hợp lệ hoặc bán kính thu được không lớn hơn \(d_0\), bộ đó được \(0\) điểm.

Nếu có kết quả nộp cho bộ dữ liệu đó đạt bán kính lớn hơn \(d_0\), gọi \(d_1\) là bán kính lớn nhất trong các kết quả đã nộp, với \(d_1>d_0\). Kết quả có bán kính \(d\) (\(d_0\le d\le d_1\)) nhận tỷ lệ điểm

Vì mỗi bộ có tối đa \(20\) điểm, số điểm nhận được cho bộ đó là \(20(d-d_0)/(d_1-d_0)\) khi \(d>d_0\).

Ví dụ

Các ví dụ sau minh họa nội dung tệp kết quả với \(n=3\) và \(n=8\); chúng không thuộc năm bộ dữ liệu cần nộp. Không có dòng chứa \(n\) trong tệp kết quả.

25000000 25000000
75000000 25000000
25000000 75000000

74540929 25404070
25474639 38662789
61538179 74593059

50993849 72645350
17399669 81993059
83110119 83073720
50245039 25147290
83063380 16879409
16948019 16965430
26471179 49375439
76212739 50011850