c807: 一維凸包問題
標籤 : set
通過比率 : 75% (9 人 / 12 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-10-25 18:29

內容

「在一個實數向量空間 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 1000000)}$ 。

接下來 $\color{black}{N}$ 行為操作內容(所有座標均為整數)。

輸出說明

每次操作後,輸出點集 $\color{black}{P}$ 凸包的頂點數目及點座標(由小到大排列)。

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

範例輸入
4
1 10
1 20
1 15
2 10 20
範例輸出
1 10
2 10 20
2 10 20
0
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (16%): 2.0s , <1M
公開 測資點#1 (16%): 2.0s , <50M
公開 測資點#2 (17%): 2.0s , <50M
公開 測資點#3 (17%): 2.0s , <50M
公開 測資點#4 (17%): 2.0s , <50M
公開 測資點#5 (17%): 2.0s , <10M
提示 :

測資點 $\color{black}{00}$,$\color{black}{N \le 1000}$。
測資點 $\color{black}{01}$,沒有第二種操作。
測資點 $\color{black}{00 \sim 05}$,$\color{black}{1 \le N \le 1000000, \space |x|, |l|, |r| \le 10^9}$。

標籤:
set
出處:
[編輯:
icube (常數爆炸)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」