Mua đồ

Xem PDF



Thời gian:
Python 3 2.0s

Tác giả:
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.

Example

Test 1

Input
3
2 2
3 3
1 1
Output
3
2.828427

Bình luận


  • 2
    huyhau6a2    8:53 p.m. 3 Tháng 1, 2022

    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

    • 5 bình luận nữa