2191 . D. 質感測試
TopCoder
Tags
Description
法國設計師「西當・普里斯」設計了一款新潮的燈具，這盞燈具的造型是一個圓盤，上面佈設了許多單顆的 LED 燈泡，開啟燈具上 LED 的方式，是利用一支與圓盤直徑等長的棒狀感應器，此感應器的中心點固定於圓盤圓心，且可順時針以圓心為固定點旋轉，旋轉時它所接觸到的 LED 皆會被開啟。以下圖為例，黑點代表未開啟的燈泡，開關由 L1 移動至 L2 後，燈泡開啟的狀況如下。
每次開啟的 LED 燈泡會落在棒狀感應器經過的兩個扇形區域。另外，我們假設旋轉開始或結束時，若感應器下方有 LED 燈泡，則它們也會被開啟。
然而，廠商在製造燈具時沒有控管材料，做出來的燈具上所佈設的 LED 亮度與顏色不一，導致整體的整體質感受到了影響。西當普里斯請廠商把每顆 LED 開啟時的呈現的質感量化為一個整數，稱為質感係數；整盞燈具的質感可由開啟的 LED 之質感係數加總而得，若一個 LED 都沒有開啟，則質感為 $0$。已知我們可以選擇感應器初始擺放的角度，在初始所有 LED 燈泡皆是關閉的狀態下，請寫程式幫助西當普里斯，計算這盞燈具最大可能的質感。
Input Format
輸入共 $n + 1$ 行，第一行有一個整數 $n$，表示 LED 燈泡的個數。假設圓心位於原點 $(0, 0)$。接下來 $n$ 行，第 i 行有三個整數 $x_i , y_i , w_i$，其中 $(x_i , y_i)$ 表示第 $i$ 個 LED 燈泡的座標，任二 LED 燈泡的座標皆不同且燈泡座標不會在原點上，$w_i$ 表示該燈泡的質感係數。
Output Format
輸出為一整數，表示此燈具的最大質感。
Sample Input 1
2 1 -1
-5 1 3
-3 1 -2
0 1 4
Sample Output 1
Sample Input 2
1 -1 -1
1 3 1
0 -1 -4
0 4 5
-1 1 1
-1 -3 1
-2 2 -2
Sample Output 2
Hints
• $1 \leq n \leq 3 \times 10^ 5$，且 $n$ 為整數。
• $x_i , y_i$ 皆為 $−10^ 5$ 到 $10^ 5$ 之間的整數 (包含 $−10^ 5$ 與 $10^ 5$)。
• $−1000 \leq w_i \leq 1000$，且 $w_i$ 為整數。
• 對所有 $1 \leq i < j \leq n$，滿足 $x_i \neq x_j$ 或 $y_i \neq y_j$。
• 對所有 $1 \leq i \leq n$，滿足 $x_i \neq 0$ 或 $y_i \neq 0$。
本題共有四組測試題組，條件限制如下所示。每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。
1. ($21\%$) 所有 LED 燈泡的 $y$ 座標相同，$n \leq 100$。
2. ($35\%$) 所有 LED 燈泡的 $y$ 座標相同，$n \leq 10^ 4$。
3. ($11\%$) $n \leq 10^ 4$。
4. ($33\%$) 無額外限制。
Problem Source
2020 TOI 入營考
testdata set by Omelet
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~9 | 所有 LED 燈泡的 $y$ 座標相同，$n \leq 100$ | 21 |
| 2 | 0~19 | 所有 LED 燈泡的 $y$ 座標相同，$n \leq 10^ 4$ | 35 |
| 3 | 0~49 | $n \leq 10^ 4$ | 11 |
| 4 | 0~59 | 無額外限制 | 33 |