Mua đồ

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Thời gian:

Python 3 2.0s

Tác giả:

huyhau6a2

Dạng bài

Điểm: 280 Thời gian: 1.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

huyhau6a2 đang có dự định mua \(n\) món đồ tại \(n\) cửa hàng khác nhau. Cửa hàng thứ \(i\) ở tọa độ \((x_i, y_i)\). huyhau6a2 đã dự định mua \(n\) món đồ và xếp thứ tự mua đồ theo \(1\) vòng tròn. Cụ thể huyhau6a2 sẽ chọn \(1\) cửa hàng để mua trước, sau đó cứ theo thứ tự vòng tròn mà mua ở những cửa hàng tiếp theo.

VD: xét \(n=5\) và nếu huyhau6a2 mua ở cửa hàng 4 trước thì ta sẽ có thứ tự mua: \((4, 5, 1, 2, 3)\); nếu mua ở cửa hàng 2 trước thì ta sẽ có thứ tự mua: \((2, 3, 4, 5, 1)\).

Hãy giúp huyhau6a2 chọn số hiệu của cửa hàng cần mua trước sao cho độ dài đường đi cần phải đi là ít nhất, và độ dài ngắn nhất đó là bao nhiêu?

Input

Dòng 1 gồm duy nhất 1 số \(n(n\le 10^5)\)
\(n\) dòng tiếp theo, mỗi dòng gồm 2 số chỉ tọa độ của cửa hàng thứ \(i(|x_i|, |y_i|\le 10^9)\).

Output

Xuất ra 2 dòng, dòng thứ nhất xuất ra số hiệu của cửa hàng cần mua trước, dòng thứ hai xuất ra độ dài của đường đi ngắn nhất, kết quả dòng 2 phải xuất kết quả sau khi làm tròn \(6\) chữ số thập phân.