Đảo nữ hoàng

View as PDF

Submit solution

Points: 350 (partial)
Time limit: 2.0s
Memory limit: 512M
Input: stdin
Output: stdout

Authors:
Problem types

Ước mơ của Lương là trở thành tỉ phú để mua cho Vy một hòn đảo. Trong giấc mơ đó, Lương đặt tên hòn đảo là đảo VH. Trên hòn đảo đó, Lương sẽ trang bị mọi tiện nghi để Vy cảm thấy mình như một nữ hoàng thực sự. Một trong số những tiện nghi cần thiết nhất là hệ thống internet và truyền hình để anh trai và em gái có thể nói chuyện với nhau ở mọi nơi trên hòn đảo.

Để thực hiện kế hoạch phủ sóng hòn đảo, Lương đã xây dựng \(n\) trạm thu phát sóng. Mỗi trạm thu phát sóng có bán kính hoạt động giống nhau là \(r\) và có thể nhận tín hiệu từ các trạm thu khác trong tầm hoạt động của nó. Nói cách khác, trạm \(A\) và \(B\) được kết nối khi và chỉ khi \(AB \leq r\). Để mua thiết bị thu phát có bán kính \(r\), Lương cần bỏ ra chi phí là \(X * r\) với \(X\) là hằng số cho trước. Lương cũng có một lựa chọn khác là sử dụng dây ngầm nối trực tiếp 2 trạm thu phát bất kỳ, mỗi đường dây sẽ tốn chi phí là \(Y\) đồng.

Lương cần kết hợp hai loại kết nối trên để đảm bảo tất cả các trạm thu phát có thể được kết nối với nhau (trực tiếp hoặc gián tiếp). Tìm chi phí nhỏ nhất Lương cần bỏ ra để chinh phục Vy (trong mơ). Lương muốn bạn trả lời câu hỏi với \(q\) truy vấn \((X, Y)\).

Input

  • Dòng đầu tiên chứa hai số tự nhiên \(n, q \ (n, q \leq 2000)\)
  • \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i, y_i \ (|x_i|, |y_i| \leq 10^5)\) tương ứng với tọa độ của trạm thu phát sóng thứ \(i\). Không có hai trạm thu nào có cùng tọa độ.
  • \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(X, Y \ (0 \leq X, Y \leq 10^9)\) tương ứng với một truy vấn.

Output

Với mỗi truy vấn, in ra một dòng là chi phí nhỏ nhất Lương cần bỏ ra để chinh phục em gái. Kết quả được chấp nhận nếu sai số không vượt quá \(10^{-6}\).

Ví dụ

Input 1

4 2
0 0
0 5
5 0
10 10
1 3
10 10000

Output 1

8.0000000000
111.8033988750

Input 2

3 2  
0 0
0 5
5 0
10 1
0 10

Output 2

2.0000000
0

Giới hạn

  • \(20 \%\) số test có \(X = 10^9, Y \leq 10^6\) và \(q \leq 10\).
  • \(20 \%\) số test có \(Y = 10^9\) và \(q \leq 10\).
  • \(30 \%\) số test có \(q \leq 10\).
  • \(30 \%\) số test còn lại không có điều kiện gì thêm.

Giải thích

Trong truy vấn 1 của test ví dụ 1, Lương chọn \(r = 5\) và chọn nối dây giữa 2 trạm \((0, 5)\) và\((10, 10)\). Chi phí bỏ ra là \(X * r + Y * 1 = 8\). Trong hình dưới, đường nối liền biểu thị đường dây ngầm, và đường gạch nối biểu thị sự kết nối thông qua thiết bị thu phát vô tuyến.

Sample1

Trong truy vấn 1 của test ví dụ 2, Lương chọn \(r = 0\) (không đặt trạm thu phát), và đặt hai đường dây ngầm nối trạm 1-3 và 1-2. Chi phí là \(2Y = 2\).


View comments (1)

Comments


  • 0
    aabbcc1122  commented on 10:18 p.m. 25 nov, 2020

    bài này làm sao vậy ạ