Mua đồ
Xem PDF
Điểm:
280
Thời gian:
1.0s
Bộ nhớ:
640M
Input:
bàn phím
Output:
màn hình
đ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)\). đã dự định mua \(n\) món đồ và xếp thứ tự mua đồ theo \(1\) vòng tròn. Cụ thể 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 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 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.
Example
Test 1
Input
3
2 2
3 3
1 1Output
3
2.828427
Bình luận
ủa rồi là sao
ui dùng long double thì ko đúng mà dùng double thì đúng ???
hay
căng
Bài này giống như tìm khoảng cách của 2 cửa hàng số hiệu gần nhau sao cho khoảng cách lớn nhất có gì mai mình phân tích tiếp nha
Bài này dễ lắm rồi nha không ac thì mình cũng chịu luôn ấy huhu