Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Hôm nay là 1 ngày đẹp trời, Jack và Rose quyết định ra ngoài thung lũng Titanic để chơi ném bóng. Trò chơi rất đơn giản, Jack và Rose đứng cách nhau 1 khoảng cách là d, sau đó Jack sẽ ném các quả bóng cho Rose, sao cho bóng phải có điểm rơi đúng vào vị trí của Rose. Do quả bóng được làm từ cao su kết tinh ngàn năm, nên độ nảy là 100%, tức nếu trc khi chạm đất bóng có vận tốc như thế nào, thì sau khi đập đất và nảy lên, độ lớn vận tốc vẫn như thế, không hề có năng lượng mất mát. Nói cách khác dễ hiểu hơn thì khi được ném chính xác thì quả bóng sẽ bay từ Jack đến Rose theo quỹ đạo parabol, hoặc là nảy nhiều lần trên mặt đất thì quỹ đạo sẽ là các parabol y hệt nhau xếp liên tiếp. Nhưng luật trò chơi là số lần bóng nảy không được vượt quá b.

Nhưng trò chơi không đơn giản như vậy, trên đoạn đường giữa 2 người có rất nhiều cột đèn, mỗi cột đèn có chiều cao là h_i và khoảng cách từ Jack đến cột đèn là p_i. Vì vậy, Jack sẽ phải tính toán, cân nhắc xem ném bóng như thế nào (góc nào, độ lớn vận tốc ban đầu của bóng bao nhiêu) để sao cho bóng tiếp đấn đúng chỗ của Rose và không chạm phải bất kỳ cột đèn nào trên đường bay. Do không muốn tốn sức nên Jack muốn vận tốc ban đầu của bóng ném ra phải là nhỏ nhất có thể. Các bạn hãy giúp Jack xác định xem vận tốc nhỏ nhất để thực hiện pha ném hoàn hảo cho Rose là bao nhiều nhé!

Biết thung lũng vô cùng rộng và bằng phẳng. Lực cản không khí có thể bỏ qua.

1 trường hợp minh họa (như hình vẽ). Trong trường hợp này Jack có thể ném bóng không nảy lần nào, hoặc nảy 1 lần, nảy 2 lần, … thì bóng đều đến được chỗ Rose. Do độ nảy là 100% và không có lực cản nên quỹ đạo là 1 parabol hoặc các parabol giống nhau xếp liên tiếp.

Để hỗ trợ trong việc tính toán, Rose có đưa cho Jack các quy ước và công thức sau:

-          Vận tốc ban đầu là v, được chia làm 2 thành phần: V_0x theo phương Ox và V_0y theo phương Oy

-          Tại thời điểm t bất kỳ, x là khoảng cách từ vị trí hiện tại của quả bóng đến vị trí ném bóng (hoặc vị trí bóng nảy), y là độ cao của quả bóng, V_x và V­_y là 2 thành phần vận tốc của quả bóng lúc đó. Gia tốc trọng trường của Trái Đất là g.

-          Ta sẽ có công thức:  V_x = V_0x = hằng số;   x = V_0x.t;   V_y = V_0y – gt;   y = gt² + V_0yt 

-          Biến đổi, ta sẽ được phương trình quỹ đạo sau:

-          Để dễ trong việc tính toán, ta chọn gia tốc trọng trường của Trái Đất g = 1.

Input

Dòng thứ nhất bao gồm 3 số tự nhiên d, n, b. d là khoảng cách giữa Jack và Rose (1 <= d <= 10000), n là số cột đèn (1 <= n <= 10), và b là số lần tối đa bóng được phép nảy (không tính lần nảy tại vị trí của Rose) (0 <= b <= 15).

n dòng tiếp theo, mỗi dòng gồm 2 số tự nhiên. Dòng thứ i bao gồm 2 số tự nhiên p_i và h_i lần lượt là khoảng cách từ Jack đến đèn, và độ cao của cột đèn (0 < p_i < d , 1 <= h_i <= 10000).

Output

In ra vận tốc ban đầu nhỏ nhất có thể của quả bóng để bóng có thể đến được vị trí của Rose mà không chạm vào bất kỳ cột đèn nào. Vận tốc ban đầu V₀ được tính theo công thức:

Kết quả in đến chữ số thập phân thứ 7 sau dầu “.”, và sai số không vượt quá 10^-6.

Example

Test 1:

Input:

100 1 0

50 100

Output:

14.5773797

Test 2:

Input:

10 1 0

4 2

Output:

3.1622777

Test 3:

Input:

100 4 3

20 10

30 10

40 10

50 10

Output:

7.7817450

Test 4:

Input:

343 3 2

56 42

190 27

286 34

Output:

11.0871046

Bảng xếp hạng ACM PTIT (NEW)