e021: 史蒂芙的泡泡
標籤 : pbds rope 射線法 空間幾何
通過比率 : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-02-21 21:56

內容

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

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

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

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

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

將一個泡泡視為一個簡單多邊形 $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。

範例輸入
5 14

0 0
10 0 
10 10
0 10
5 5

1 0 0
1 1 0
1 2 1
1 3 2
3 5.5 5
3 10 -1
3 10 5
1 4 1
3 5.5 5
3 10 -1
3 10 5
2 3
3 5 7.5
3 5 2.5
範例輸出
1
0
0
0
0
0
0
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 射線法 空間幾何
出處:
工作幻想 [編輯:
morris1028 (碼畜)
]


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