trang chủ / đề bài / icpcwf24_f

Cạnh tranh thân thiện

Đề bài

Mô tả

Ban lãnh đạo Liên minh Quốc tế vì Biến đổi Hành tinh (ICPC), một tổ chức phi lợi nhuận đấu tranh nâng cao nhận thức về môi trường, lo ngại rằng các chi hội khu vực của họ chưa làm đủ để tạo ra tác động thực sự trong việc chống biến đổi khí hậu. Lấy cảm hứng từ những nghiên cứu mới nhất cho thấy cạnh tranh là một trong những động lực tốt nhất, họ quyết định tổ chức một cuộc thi giữa các chi hội.

Đồng thời, ICPC không muốn làm chậm việc lan tỏa ý tưởng. Để khuyến khích các chi hội chia sẻ những phương pháp chống biến đổi khí hậu hiệu quả, ICPC quyết định chia 2n chi hội của mình thành hai đội: đội xanh lá và đội xanh dương. Để cân bằng, mỗi đội phải gồm đúng n chi hội.

Để hai đội không cản trở nhau, ICPC muốn hai đội ở càng xa nhau càng tốt. Cụ thể, khoảng cách Euclid giữa cặp chi hội gần nhau nhất thuộc hai đội khác nhau phải lớn nhất có thể.

Hãy giúp ICPC chia đội theo các quy tắc trên.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên n (1≤n≤500): số chi hội của mỗi đội. Các chi hội được đánh số từ 1 đến 2n.

Mỗi dòng trong 2n dòng tiếp theo chứa hai số nguyên xi và yi (−109≤xi,yi≤109): tọa độ Descartes của vị trí chi hội thứ i. Các chi hội ở các vị trí đôi một khác nhau.

Dữ liệu ra

In ra n+1 số. Số đầu tiên là khoảng cách giữa hai chi hội gần nhau nhất thuộc hai đội khác nhau. n số tiếp theo là số hiệu các chi hội thuộc đội xanh dương. Nếu có nhiều cách chia đội cùng đạt khoảng cách tối ưu, in ra cách bất kỳ.

Khoảng cách được chấp nhận nếu sai số tuyệt đối hoặc tương đối không quá 10−6.

Ràng buộc

  • 1≤n≤500.
  • −109≤xi,yi≤109, các điểm (xi,yi) đôi một khác nhau.

Ví dụ

Input Output Giải thích
2
0 1
1 0
1 1
0 0
1.000000
1
2
Bốn chi hội là bốn đỉnh của hình vuông cạnh 1. Đội xanh dương gồm (0,1) và (1,0), đội xanh lá gồm (1,1) và (0,0): mọi cặp khác đội đều cách nhau 1. Cách chia nào cũng có một cặp khác đội là hai đỉnh kề nhau, nên không thể vượt quá 1.
2
0 1
-1 -1
1 0
2 2
2.236068
4
2
Đội xanh dương gồm (2,2) và (−1,−1), đội xanh lá gồm (0,1) và (1,0). Cả bốn cặp khác đội đều cách nhau 5≈2,236068.
3
0 0
1 1
2 2
3 3
4 4
5 5
1.414214
1
2
3
Sáu chi hội nằm trên một đường thẳng, hai chi hội liên tiếp cách nhau 2. Chia thành ba chi hội đầu và ba chi hội cuối, cặp khác đội gần nhất là (2,2) và (3,3), cách nhau 2≈1,414214.

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