Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VOTELPH - Bà Nà

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/votelph


Sau thành công của Bà Nà - Đường lên tiên cảnh, Alex muốn đầu tư vào một dự án du lịch khác trên dãy núi Trường sơn. Cùng với đoàn thám hiểm miệt mài tìm kiếm, cuối cùng Alex cũng tìm được một địa điểm vô cùng lý tưởng để khởi công xây dựng dự án này. 

Vùng núi gồm N ngọn núi mà Alex chọn có cấu trúc rất đặc biệt. Nếu quan sát trên bản đồ 2D (mặt phẳng tọa độ Oxy) thì mỗi ngọn núi có thể được biểu diễn bởi một đường Parabola có phương trình là ax2 + bx + c (với a < 0). Trên bản đồ này, Alex tiến hành thiết kế các tuyến cáp treo. Có Q tuyến cáp treo sẽ được quy hoạch, vị trí cụ thể của điểm khởi đầu và điểm kết thúc của chúng chưa được xác định vì chưa có bản thống kê kinh phí chi tiết. Tuy nhiên, theo dự kiến ban đầu thì tuyến cáp treo thứ i sẽ bắt đầu tại hoành độ Li và kết thúc tại hoành độ Ri trên bản đồ 2D.

Alex đặt AN TOÀN lên mọi tiêu chí trong quá trình thi công dự án này. Có hai điều Alex quan tâm nhất:

  • Để cho du khách có cảm giác an toàn nhất, độ cao của cáp treo so với mực nước biển sẽ không đổi trong suốt đường đi. Nói cách khác, tuyến cáp treo có thể được mô tả bởi một đường thẳng song song với trục x của bản đồ 2D. 
  • Độ cao của cáp sẽ phải lớn hơn độ cao của tất cả các ngọn núi mà nó đi qua ít nhất 1 đơn vị. Cụ thể hơn, nếu Hi là độ cao của tuyến cáp treo thứ i, thì Hi = 1 + max(akx2 + bkx + ck | 1 ≤ k ≤ N và Li ≤ x ≤ Ri)  (ak, bk, ck là thông số của Parabola biểu diễn ngọn núi thứ k).

Bạn hãy giúp Alex tính toán độ cao an toàn tối thiểu của mỗi đường cáp treo nhé.

Input

  • Dòng đầu chứa 2 số nguyên NQ tương ứng với số đỉnh núi và số tuyến cáp treo.
  • Dòng thứ i trong số N dòng tiếp theo chứa 3 số thực ai, bici mô tả ngọn núi thứ i.
  • Dòng thứ i trong số Q dòng cuối chứa 2 số thực Li Ri mô tả tuyến cáp treo thứ i.

Output

  • Xuất ra Q dòng, dòng thứ i chứa 1 số thực là độ cao Hi tìm được cho mỗi tuyến cáp treo, với ít nhất 2 chữ số sau dấu phẩy.

Giới hạn

  • Subtask 1 (30%): 1 ≤ N ≤ 300, 1 ≤ Q ≤ 10000
  • Subtask 2 (30%): 1 ≤ N ≤ 300, 1 ≤ Q ≤ 500000 
  • Subtask 3 (40%): 1 ≤ N ≤ 2000, 1 ≤ Q ≤ 500000

Ngoài ra trong tất cả các test:

  • -10 ≤ ai < 0
  • -103 ≤ bi, ci ≤ 103
  • -103 ≤ Li ≤ Ri ≤ 103
  • Các số trong input có không quá 2 chữ số sau dấu phẩy

Ví dụ

Input:

2 3

-1.0 3.0 0.0

-1.0 0.0 6.0

-1.0 0.4

1.0 2.0

2.5 3.0

Output:

7.00

6.00

2.25

Chấm điểm

  • Đáp số của bạn được coi là đúng nếu đáp án của bạn và ban tổ chức chênh nhau không quá 10-2
  • Trong thời gian thi, bài của bạn sẽ chỉ được chấm với duy nhất 1 test có trong đề bài.

Hình minh họa  

 

VOTELPH Example

Chú thích: 2 ngọn núi tương ứng với 2 parabola, 3 tuyến cáp treo được biểu diễn bởi các đoạn thẳng màu đen trên trục hoành, 3 điểm màu đỏ là độ cao lớn nhất của các ngọn núi mà các tuyến cáp treo tương ứng đi qua.


Được gửi lên bởi:VOJ Team
Ngày:2013-12-19
Thời gian chạy:1.5s-2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VNOI Online 14 - Trần Anh Hướng Thái Huy

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.