Problem H
サウナ
しかし、仲間といると問題が発生することが多いです。サウナを使うときに一番大切なのは、温度を正しく設定することです。 フィンランド人はサウナの温度にうるさいのです。 人によって許容できる最高温度が異なります。 ある人にとって温度が高すぎると、その人は帰ってしまいます。 また、耐えられる温度範囲内では、温度によって幸福度が異なります。 人の幸福度は、二次関数（$ax^2 + bx + c$で表される）に従います。
たくさんのフィンランド人がサウナを利用しており、あなたの助けを必要としています。 サウナの温度が最適に設定されていた場合の、幸福度の合計の最大値を求めてください。 サウナの温度がある人の許容できる温度よりも高く設定されている場合、その人は幸福度の総和に何の貢献もしていません（家に帰ってしまいました）。 温度はケルビンで与えられ、下限は$0 \textrm{ K}$、上限は$100,000 \textrm{ K}$です。
入力
最初の行には整数の $1 \le N \le 100,000$ が含まれており、フィンランド人の人数を表します。 その後の $N$ 行は、それぞれのフィンランド人に対応します。 各行には、４つの整数 $a,b,c,t$ ($-10^9 \le a,b,c \le 10^9, 1 \le t \le 100,000$) が含まれていて、フィンランド人の幸福関数 $ax^2 + bx + c$ と、許容できる温度の範囲が $0 \textrm{ K}$ 以上 $t\textrm{ K}$ 以下であること（それぞれ境界値は含まれる）を表しています。 この関数は、$0$と$t$の間のすべての値に対して正であることが保証されています。
出力
温度を正しく設定した場合に得られる最大の幸福度を1つの数で出力してください。 相対誤差または絶対誤差が $10^{-5}$ 以下であれば正解とします。
得点
あなたのソリューションは複数のテストケースグループでテストされます。グループのポイントを得るためには、あなたのソリューションはグループ内のすべてのテストケースに成功しなければなりません。
|
Group |
Point value |
Bounds |
|
$1$ |
$21$ |
$N \le 1000$, 全ての $t$ は等しい。 |
|
$2$ |
$29$ |
$N \le 1000$, 全ての $a$ は正（すなわち、フィンランド人は熱いサウナが好き）。 |
|
$3$ |
$38$ |
$N \le 1000$, 全ての $a$ は負。 |
|
$4$ |
$12$ |
追加の制約はなし。 |
サンプル1の説明
このケースでは、最適温度は $0 \textrm{ K}$ です。 2人とも同じ幸福度 $1 \cdot 0^2 -6\cdot 0 + 10 = 10$ となります。 幸福度の合計は $10 + 10 = 20$ となります。
サンプル2の説明
このケースでは、最適温度は $\frac{10}{3} \textrm{K}$ です。 1人目の幸福度は、$-3(\frac{10}{3})^2 + 20 \cdot \frac{10}{3} + 3 = -\frac{100}{3} + \frac{200}{3} + 3 = 36 + \frac{1}{3}$ です。 2人目のは、温度が高いので家に帰ります（彼女は、$1\textrm{ K}$までしか温度を許容しません）。 よって、合計の幸福度は、$36 + \frac{1}{3}$となります。
| サンプル入力 1 | サンプル出力 1 |
|---|---|
2 1 -6 10 4 1 -6 10 7 |
20.0000000000 |
| サンプル入力 2 | サンプル出力 2 |
|---|---|
2 -3 20 3 5 -1 0 2 1 |
36.3333333333 |
| サンプル入力 3 | サンプル出力 3 |
|---|---|
1 1000000 2 3 10000 |
100000000020003.0000000000 |
