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 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 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 (): số chi hội của mỗi đội. Các chi hội được đánh số từ đến .
Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và (): tọa độ Descartes của vị trí chi hội thứ . Các chi hội ở các vị trí đôi một khác nhau.
Dữ liệu ra
In ra 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. 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á .
Ràng buộc
- .
- , các điểm đô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 . Đội xanh dương gồm và , đội xanh lá gồm và : mọi cặp khác đội đều cách nhau . 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á . |
| 2 0 1 -1 -1 1 0 2 2 |
2.236068 4 2 |
Đội xanh dương gồm và , đội xanh lá gồm và . Cả bốn cặp khác đội đều cách nhau . |
| 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 . 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à và , cách nhau . |
Bình luận