JOI 2007 Representative Selection - Ngày 4

Croatia đang triển khai kế hoạch nối tất cả các thành phố trong nước bằng mạng cáp quang. Cáp quang cho phép liên lạc nhanh và chất lượng cao, ngay cả khi thông tin phải đi qua nhiều thành phố trung gian. Chẳng hạn, nếu có cáp nối \(A_i\) với \(A_{i+1}\) với mọi \(1\le i<k\), thì \(A_1\) và \(A_k\) có thể liên lạc với nhau qua mạng cáp quang.

Chính phủ muốn mọi cặp thành phố đều có thể liên lạc qua mạng này. Tuy nhiên, có nhiều doanh nghiệp lắp đặt cáp, nên chưa có ai nắm được toàn bộ mạng hiện tại. Dựa trên thông tin do các doanh nghiệp cung cấp, hãy tính số tuyến cáp quang ít nhất cần lắp thêm để mọi cặp thành phố đều có thể liên lạc với nhau.

Mỗi tuyến cáp nối hai thành phố và cho phép liên lạc theo cả hai chiều.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(n\), là số thành phố. Các thành phố được đánh số từ \(1\) đến \(n\).
• Dòng thứ hai chứa số nguyên \(m\), là số tuyến cáp quang đã được lắp đặt.
• Dòng thứ \(i+2\) (\(1\le i\le m\)) chứa hai số nguyên khác nhau \(a_i,b_i\), phân cách bằng dấu cách, cho biết có một tuyến cáp nối hai thành phố \(a_i\) và \(b_i\).

Có thể có nhiều tuyến cáp giữa cùng một cặp thành phố.

Dữ liệu ra

Ghi ra đầu ra chuẩn số tuyến cáp quang ít nhất cần lắp thêm để mọi cặp thành phố đều có thể liên lạc qua mạng. Nếu mạng hiện tại đã đáp ứng yêu cầu, ghi 0.

Ràng buộc

• \(1\le n\le10\,000\).
• \(1\le m\le30\,000\).
• \(1\le a_i,b_i\le n\) và \(a_i\ne b_i\) (\(1\le i\le m\)).

Phân nhóm

Các bộ dữ liệu được chấm độc lập; không có điều kiện ràng buộc riêng cho từng nhóm.

• Các bộ dữ liệu \(01\)–\(05\): \(20\) điểm mỗi bộ, tổng cộng \(100\) điểm; áp dụng toàn bộ ràng buộc trên.

Ví dụ

8
7
3 5
4 1
5 4
7 5
4 7
1 4
6 8

2

Cho \(N\) đường thẳng \(\ell_1,\ell_2,\ldots,\ell_N\) trên mặt phẳng. Hãy tính số miền mà chúng chia mặt phẳng thành. Các đường thẳng được cho có thể trùng nhau.

Chẳng hạn, xét năm đường thẳng trong đó \(\ell_1\) song song với \(\ell_2\), ba đường \(\ell_2,\ell_3,\ell_4\) đi qua cùng một điểm, các cặp đường còn lại đều cắt nhau và không có bộ ba đồng quy nào khác. Chúng chia mặt phẳng thành \(14\) miền.

Dữ liệu vào

Đọc từ đầu vào chuẩn, gồm \(N+1\) dòng:

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ \(i+1\) (\(1\le i\le N\)) chứa bốn số nguyên \(a_i,b_i,c_i,d_i\), phân cách bằng dấu cách. Đường thẳng \(\ell_i\) đi qua hai điểm phân biệt \(P_i=(a_i,b_i)\) và \(Q_i=(c_i,d_i)\).

Mỗi đối tượng được cho là toàn bộ đường thẳng qua hai điểm, không chỉ là đoạn thẳng nối chúng.

Dữ liệu ra

Ghi ra đầu ra chuẩn số miền trên một dòng.

Ràng buộc

• \(1\le N\le1000\).
• \(0\le a_i,b_i,c_i,d_i\le1000\) (\(1\le i\le N\)).
• \((a_i,b_i)\ne(c_i,d_i)\) (\(1\le i\le N\)).
• Các đường thẳng có thể trùng nhau, song song hoặc có nhiều đường đi qua cùng một điểm.

Phân nhóm

Các bộ dữ liệu được chấm độc lập; không có điều kiện ràng buộc riêng cho từng nhóm.

• Các bộ dữ liệu \(01\)–\(10\): \(10\) điểm mỗi bộ, tổng cộng \(100\) điểm; áp dụng toàn bộ ràng buộc trên.

Ví dụ

4
0 4 6 4
0 0 6 6
1 0 1 6
0 6 6 0

11

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