程式解題社網站 程式解題社網站上線了！
NTUCPC OJ 現在支援 Rust ！
NTUCPCPC 2026 初賽 & 決賽題目已公開！ 連結
YTP 2026 題目已公開！ 連結
1517 . 拋物線
TopCoder
Tags
Description
你有玩過憤怒鳥 (Angry Birds) 嗎？憤怒鳥是一款用彈弓操控小鳥，來攻擊建築物與小豬的遊戲。裡面的小鳥被彈弓發射後，都會按照拋物線的軌跡飛行。
方塊國的國王是憤怒鳥系列的忠實粉絲，因此每年方塊國國慶時，方塊國的國王在方塊國的首都的方塊大道發射拋物線軌跡的憤怒的小方塊煙火。每年幾乎所有的方塊國國民們都非常期待小方塊煙火，只有一群方塊不喜歡，就是方塊大道上的居民們。
方塊大道是一條東西向無限長的大道，可以想像成一個座標平面 $(x, y)$ 的 $x$ 軸。每個 $x$ 座標為整數的點是一棟大樓的位置，每棟大樓都是一個無限高的大樓，在每個 $y$ 座標為正整數的點都有一戶居民。也就是說每個 $(x, y)$ 皆為整數，$y > 0$ 的點都是一戶居民。方塊大道的居民之所以不喜歡小方塊煙火，是因為煙火發射時如果軌跡有經過他們家相對位置以上的地方，那麼煙火的落塵就會飄入他們的家中。
更準確地說，我們可以把一枚被發射的小方塊煙火看成一個在這個 $x,y$ 平面上、開口朝下、最高點 $> 0$ 的拋物線。假設煙火發射時的軌跡為 $y = ax^ 2 + bx + c$，那麼對於每個整數 $x^ \star$，任何一戶住在滿足 $0 < y^ \star \le ax^ {\star2} + b x^ \star + c$ 的 $(x^ \star, y^ \star)$ 的居民都會受到落塵影響。也就是說，假設發射了 $n$ 座煙火，第 $i$ 座的軌跡為 $y = a_ix^ 2 + b_i x + c_i$，對於任何一戶居民 $(x', y')$，只要存在 $i$ 使得 $y' \le a_ix'^ 2 + b_ix' + c_i$ ，$(x', y')$ 就是一戶受到影響的居民。
做為今年的煙火活動的工作人員，你已經預先知道今年每個小方塊煙火的發射軌跡。方塊國王想要請你統計有多少戶居民受到影響，以補償他們受到的損失，並威脅如果你做不到的話就要把你跟小方塊煙火一起丟到空中。為了避免被丟到空中，你可以做出這個問題嗎？
如果你不喜歡小方塊，這邊是一個簡易的題目敘述：
給定 $n$ 個拋物線形式的限制，$y \le a_ix^ 2 + b_ix + c_i$，$a_i < 0$，問滿足這 $n$ 個限制中至少一個，且 $y> 0$ 的格子點 $(x, y)$ 共有多少個？其中格子點的定義為 $x, y$ 座標皆為整數的點。
Input Format
第一行包含一個整數 $n$，代表發射的煙火座數。
接下來 $n$ 行，第 $i$ 行包含三個整數 $a_i, b_i, c_i$，代表第 $i$ 座煙火的軌跡為 $y = a_i x^ 2 + b_i x + c_i$。
- $1 \leq n \leq 5 \times 10^ 5$
- $-10^ 6 \leq a_i \leq -1$
- $-10^ 6 \leq b_i \leq 10^ 6$
- $-10^ {11} \leq c_i \leq 10^ {11}$
- $a_i, b_i, c_i$ 皆為整數
- 保證每條拋物線的最高點的 $y$ 座標大於 $0$，亦即 $b_i^ 2 - 4 a_i c_i > 0$
Output Format
輸出一個整數，代表受到落塵影響的居民戶數，也就是滿足 $y > 0$ 且至少存在一座煙火 $i$ 使得 $y \leq a_i x^ 2 + b_i x + c_i$ 的格子點 $(x, y)$ 數量。
保證答案不會超過帶號 64 位元整數所能表示的範圍。
Sample Input 1
2 -1 0 4 -1 4 0
Sample Output 1
17
Sample Input 2
1 -2 3 -1
Sample Output 2
0
Hints
範測 1 解釋：
兩條拋物線分別為 $y = -x^ 2 + 4$ 與 $y = -x^ 2 + 4x$。逐一檢查每個 $x$ 上兩者取 $\max$ 後的高度：
| $x$ | $-2$ | $-1$ | $0$ | $1$ | $2$ | $3$ | $4$ |
|---|---|---|---|---|---|---|---|
| $-x^ 2 + 4$ | $0$ | $3$ | $4$ | $3$ | $0$ | $-5$ | $-12$ |
| $-x^ 2 + 4x$ | $-12$ | $-5$ | $0$ | $3$ | $4$ | $3$ | $0$ |
| 取 $\max$ | $0$ | $3$ | $4$ | $3$ | $4$ | $3$ | $0$ |
$x = -1, 0, 1, 2, 3$ 分別貢獻 $3, 4, 3, 4, 3$ 個格子點；其餘的 $x$ 高度不到 $1$，不含任何滿足 $y > 0$ 的格子點。總共 $3 + 4 + 3 + 4 + 3 = 17$ 個。
範測 2 解釋：
只有一條拋物線 $y = -2x^ 2 + 3x - 1$，它的最高點在 $x = \tfrac{3}{4}$ 處，高度只有 $\tfrac{1}{8}$，因此沒有任何格子點同時滿足 $y > 0$ 與 $y \leq -2x^ 2 + 3x - 1$。答案為 $0$。
Problem Source
2026 YTP 高中組決賽 p16
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測試資料 | 0 |
| 2 | 0~8 | $n \leq 2000$ 且 $|b_i|, |c_i| \leq 2000$ | 3 |
| 3 | 0~15 | $n \leq 2000$ | 7 |
| 4 | 0~23 | $n \leq 2 \times 10^ 5$ | 14 |
| 5 | 0~33 | 無額外限制 | 1 |