c807. 一維凸包問題 - 高中生程式解題系統

內容

「在一個實數向量空間 V 中，對於給定集合 X，所有包含 X 的凸集的交集 S 被稱為 X 的凸包。」—維基百科

「在多維空間中有一群散佈各處的點，凸包是包覆這群點的所有外殼當中，表面積暨容積最小的一個外殼。」－演算法筆記。

綜合上述，我們可以很輕易地給出一維凸包的定義：
對於一條直線上的若干個點，找出長度最小的線段使得這些點都落在線段上。

請你寫一個維護一維凸包的程式，支援以下兩種操作：
$1 x :$ 插入座標 $x$ 的點到點集 $P$ 。
$2 l r :$ 移除所有座標落在 $[l, r]$ 的點。

輸入說明

第一行為操作次數 $N (1 \leq N \leq 500000)$ 。

接下來 $N$ 行為操作內容（所有座標均為整數）。

輸出說明

每次操作後，輸出點集 $P$ 凸包的頂點數目及點座標（由小到大排列）。

如果點集中沒有任何點，輸出 0 。

範例輸入 #1

範例輸出 #1

測資資訊：

記憶體限制： 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

提示：

測資點 $00$ ， $N \leq 1000$ 。
測資點 $01$ ，沒有第二種操作。
測資點 $00 \sim 05$ ， $1 \leq N \leq 500000, | x |, | l |, | r | \leq 10^{9}$ 。

2019/05/12 調整測資範圍並重測。（1e6 / 2.0s => 5e5 / 1.5s）

標籤:

出處:

[管理者： icube (!@#$%^&*()_...) ]

編號	身分	題目	主題	人氣	發表日期
45265	rsj00008 (二信008)	c807	c++可以用set	50	2025-02-03 20:54