e021. 史蒂芙的泡泡 - 高中生程式解題系統

內容

在處理完數以百計的政事後，受盡折磨的史蒂芙，打算回家好好地休息。拖著疲倦的身軀，再也無法再容納任何一點複雜計算。從王宮走回寢居的路上，發現身邊所見的事物都不再圓滑，看起來就像是粗糙的幾何多邊形構成的一切。

打算享受著泡泡浴的史蒂芙，看著眼前的多邊形泡泡，失去原本應有的色澤，那透涼的心境更蒙上了一層灰影

「為什麼是我呢？」感嘆道

伸出手戳著眼前的泡泡，卻飄了過去

「區區的泡泡也跟我作對，嗚嗚」

將一個泡泡視為一個簡單多邊形 $A$，方便起見用一個序列 $a_0, a_1, ..., a_{n-1}$ 表示多邊形 $A$ 的每一個頂點，則會有 $n$ 個線段 $\overline{a_0 a_1}, \overline{a_1 a_2}, \cdots, \overline{a_{n-1} a_0}$。

泡泡從無開始慢慢變化，增加或減少一個點，保證一直保持著簡單多邊形的特性，想要嘗試戳泡泡的史蒂芙，請幫忙她是否有機會戳到泡泡。

輸入說明

只有一組測試資料。第一行包含兩個整數 $N$, $M$，分別為平面點的個數與詢問操作個數。第一部分包含 $N$ 行兩個整數 $x$, $y$，為點 $p_i$ 平面座標值，編號從 $0$ 開始。第二部分包含 $M$ 行詢問操作，每行操作格式有以下三種：

$1$ $u$ $k$：將點 $p_u$ 插入到序列 $a$ 位置 $k$ 上，意即 $a_k = p_u$。
$2$ $k$：將位置 $a_k$ 上的點從序列 $A$ 移除，
$3$ $f_x$ $f_y$：詢問點 $(f_x, f_y)$ 是否嚴格在多邊形內部，意即在多邊形上屬於外部。

條件限制

$1 \le N, M \le 10^5$
$0 \le u < N$
$k$ 符合當前的多邊形點數限制
$f_x, f_y$ 為實數，小數點最多兩位
$-10^9 \le x, y, f_x, f_y \le 10^9$

輸出說明

對於每個操作 3，若點在多邊形內部輸出一行整數 1，反之為 0。

範例輸入 #1

範例輸出 #1

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (11%): 1.0s , <1K
公開測資點#1 (11%): 1.0s , <1M
公開測資點#2 (11%): 1.0s , <1M
公開測資點#3 (11%): 1.0s , <10M
公開測資點#4 (11%): 1.0s , <10M
公開測資點#5 (11%): 1.0s , <10M
公開測資點#6 (11%): 1.0s , <10M
公開測資點#7 (11%): 1.0s , <10M
公開測資點#8 (12%): 1.0s , <10M

提示：

5 14

0 0
10 0 
10 10
0 10
5 5

1 0 0    // 多邊形序列 A = [0] 一個點 (0, 0)
1 1 0    // 多邊形序列 A = [1, 0] 一條線 Line((10, 0), (0, 0))
1 2 1    // 多邊形序列 A = [1, 2, 0] 三角形 Polygon((10, 0), (10, 10), (0, 0))
1 3 2    // 多邊形序列 A = [1, 2, 3, 0] 矩形 Polygon((10, 0), (10, 10), (0, 10), (0, 0))
3 5.5 5  
3 10 -1
3 10 5
1 4 1    // 多邊形序列 A = [1, 4, 2, 3, 0] 一個凹口多邊形 Polygon((10, 0), (5, 5), (10, 10), (0, 10), (0, 0))
3 5.5 5
3 10 -1
3 10 5
2 3      // 多邊形序列 A = [1, 4, 2, 0] 三角形 Polygon((10, 0), (5, 5), (0, 10), (0, 0))
3 5 7.5
3 5 2.5

標籤:

pbds rope 射線法空間幾何

出處:

工作幻想 [管理者： morris821028@gmail.com

morris1028 (碼畜) ]

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