#275. Đường cong (Mã bài: CURVES)

Bộ nhớ: 512 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Khi làm bài tập về nhà, Tí gặp n hàm số bậc hai S_i(x)= ax^2 + bx + c . Cậu ấy nảy ra ý tưởng thiết kế một hàm số mới F(x) = \max\{S_i(x)\}, i = 1\ldots n .

Bây giờ Tí muốn tìm giá trị nhỏ nhất của hàm số này trên đoạn [0,1000] . Yêu cầu kết quả chính xác đến 4 chữ số sau dấu phẩy (làm tròn).

Dữ liệu:

  • Dữ liệu vào gồm T bộ dữ liệu (test cases). Dòng đầu tiên của mỗi bộ chứa số nguyên n .
  • Tiếp theo là n dòng, mỗi dòng chứa 3 số nguyên a, b, c biểu thị các hệ số của một hàm bậc hai. Lưu ý: Hàm bậc hai có thể suy biến thành hàm bậc nhất (khi a=0 ).

Kết quả:

  • Với mỗi bộ dữ liệu, xuất ra một dòng biểu thị giá trị nhỏ nhất của hàm F(x) trên đoạn [0,1000] . Kết quả làm tròn đến 4 chữ số thập phân.

Ví dụ:

Dữ liệu:

2
1
2 0 0
2
2 0 0
2 -4 2

Kết quả:

0.0000
0.5000

Giới hạn:

  • Với 50\% dữ liệu, 1 \leq n \leq 100 .
  • Với 100\% dữ liệu, 1 \leq T \leq 10 , 1 \leq n \leq 10^5 , 0 \leq a \leq 100 , 0 \leq |b| \leq 5000 , 0 \leq |c| \leq 5000 .