內容
「在一個實數向量空間 V 中，對於給定集合 X，所有包含 X 的凸集的交集 S 被稱為 X 的凸包。」—維基百科
「在多維空間中有一群散佈各處的點，凸包是包覆這群點的所有外殼當中，表面積暨容積最小的一個外殼。」－演算法筆記。
綜合上述，我們可以很輕易地給出一維凸包的定義：
對於一條直線上的若干個點，找出長度最小的線段使得這些點都落在線段上。
請你寫一個維護一維凸包的程式，支援以下兩種操作：
$\color{black}{1 \space x: }$ 插入座標 $\color{black}{x}$ 的點到點集 $\color{black}{P}$。
$\color{black}{2 \space l \space r: }$ 移除所有座標落在 $\color{black}{[l, r]}$ 的點。
輸入說明
第一行為操作次數 $\color{black}{N (1 \le N \le 500000)}$ 。
接下來 $\color{black}{N}$ 行為操作內容（所有座標均為整數）。
輸出說明
每次操作後，輸出點集 $\color{black}{P}$ 凸包的頂點數目及點座標（由小到大排列）。
如果點集中沒有任何點，輸出 0 。
範例輸入
#1
4 1 10 1 20 1 15 2 10 20
範例輸出
#1
1 10 2 10 20 2 10 20 0
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (16%): 1.5s , <1M
公開 測資點#1 (16%): 1.5s , <10M
公開 測資點#2 (17%): 1.5s , <10M
公開 測資點#3 (17%): 1.5s , <10M
公開 測資點#4 (17%): 1.5s , <10M
公開 測資點#5 (17%): 1.5s , <10M
公開 測資點#0 (16%): 1.5s , <1M
公開 測資點#1 (16%): 1.5s , <10M
公開 測資點#2 (17%): 1.5s , <10M
公開 測資點#3 (17%): 1.5s , <10M
公開 測資點#4 (17%): 1.5s , <10M
公開 測資點#5 (17%): 1.5s , <10M
提示 ：
測資點 $\color{black}{00}$，$\color{black}{N \le 1000}$。
測資點 $\color{black}{01}$，沒有第二種操作。
測資點 $\color{black}{00 \sim 05}$，$\color{black}{1 \le N \le 500000, \space |x|, |l|, |r| \le 10^9}$。
2019/05/12 調整測資範圍並重測。（1e6 / 2.0s => 5e5 / 1.5s）
標籤:
出處:
[管理者：
icube
(!@#$%^&*()_...)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||