信息學集訓隊作業(yè)

1、IOI2003 中國國家集訓隊難題活動0012gifmerge解題湖南長郡中學【題目大意】題目先輸入由空間中 n 個整數(shù)點的點集 S，然后輸入 m 個點，要你依次判斷這些點是否被包含在點集中若干點的空間多邊形中?！窘鉀Q情況】已經(jīng)解決，時間復雜度為 O(NlogN)。【算法梗概】將空間問題轉(zhuǎn)化到平面上解決，通過求半平面交，判斷是否包含在空間凸包中?！臼斋@與感謝】自己開始時只知道法可解此題，但是通過才知道還可以通過向量法解決?！菊摹窟@明顯是道幾何問題，但是如何做，既簡單，又高效呢？首先一種想法就是，如果一個點被點集中若干點的空間圖形所包含，那么必被點集中 4 個點所的三棱錐包含。那么，第一種想法

2、就是，枚舉所有的三棱錐，然后判斷點是否在此三棱錐中。但是這樣做的復雜度太高了。其次可以想到的就是求出空間凸包，然后判斷點是否在空間凸包中，但是這種方法很繁瑣，不易實現(xiàn)。下面探討簡便的方法，先從二維問題入手：判斷一個點 A 是否在平面點集中若干點的平面多邊形中。對這個問題當然有很多計算方法，但是大部分引申到空間問題很復雜，但有一種方法，卻相對比較簡單：如果存在一條過點 A 的直線，使得點集中的點都在直線的一側(cè)，那么為否，否則，為真。存在這樣的直線。無論如何旋轉(zhuǎn)直線，都不滿足。判斷這樣的直線是否存在很簡單，假設點 A 在原點，滿足要求的直線為 ax+by = 0，那么只要判斷是否存在 a, b，滿

3、足對點集中所有點都滿足 a*xi+b*yi 0。擴展到空間，就相當于找到一個相應的平面，使得點集中的所有點都分居直線一側(cè)，假設要判斷點為 A，原始坐標為（x0, y0），點集中的點為(xi，yi)，i1.n，那么將所有點移動，使得 A 與原點重合，這樣 A 點的坐標變?yōu)?0, 0),點集中的點的坐標修改為（xi-x0,yi-y0），i1.n。那么就相當于找一個過原點的平面使得其他點在平面的一側(cè)，設滿足條件的平面為 ax +by +cz = 0。那么判斷是否存在相應的 a, b, c 使得點集中所有的點，滿足 a*xi+b*yi+c*zi 0。如何判斷是否存在這樣的 a, b, c 呢？轉(zhuǎn)化一下

4、：如果 c = 0，那么只要判斷，是否存在相應的 a, b 滿足 a*xi + b*yi 0。如果 c 0，那么兩邊同除以 c, a/c*xi + b/c*yi - zi(假設 c 0，c -zi。如果 c 0，那么兩邊同時除以 c，a/c*xi + b/c*yi zi。這樣無論哪種情況，都只需判斷若干二元不等式組是否存在根，而這個問題就是我們所熟知的半平面交問題。也就是說，每個不等式 a*xi +b*yi zi 的解，可以看作平面上直線 a*xi + b*yi - zi =0上方半個平面，最后計算出所有半平面的交，如果這個交為空集，則問題為否；否則，為真。平面 ax1 + by1 z1平面 ax2 + by2 z2平面 ax2 + by2 z2平面 ax1 + by1 z1求半平面交問題的復雜度為 O(NlogN)，共要求解 N 次半平面交，所以總個算法的時間復雜度為 O(MNlogN)。