集訓隊作業(yè)dwarfs解題報告

IOI2003中國國家集訓隊難題討論活動0007《Dwarfs》解題報告安徽省蕪湖市第一中學許智磊【題目大意】給定平面上的n個點的坐標，依次給出m條直線（用直線上的兩個點來表示），求出每條直線是否把這些點分在了兩邊?！窘鉀Q情況】先求所有點的凸包V，再對每條直線二分求解，時間復雜度O((n+m)logn)，空間復雜度O(n)。【算法梗概】首先求出這些點的一個凸包，采用經(jīng)典的O(nlogn)算法。求出之后就只需要考慮凸包上的點。然后對每條直線，采用二分的方法來判斷是否穿過這個凸包?！菊摹靠吹筋}目后我們首先很容易看出：一條直線把某些點分在兩邊的充要條件是它穿過這些點的凸包V。更嚴格的證明如下：定理1：直線L把平面上一個點集S中的點分成兩部分的充要條件是L穿過S的凸包V，所謂“穿過凸包”就是把凸包中的點分成了兩部分。證明：充分性易證：如果L穿過V，那么L就把V中的點分成了兩部分，自然也就將S中的點分成兩部分。必要性：假設L不穿過V而又把S分成兩部分，也就是說S中一些點在L劃分出的半平面A內，而另一些點在另一個半平面B內。L不穿過V，所以V中所有的點都在一個半平面內（設為A），那么半平面B內的點不可能處于凸包V內，也就是說S中存在一些點不被S的凸包所包含，而這是不可能的。綜上所述，定理1得證。根據(jù)定理1，判斷一條直線L是否把點集S分成兩部分等價于判斷L是否穿過S的凸包V，也就是說，S\V中的點都是不影響判斷結果的，所以我們把這些沒有用的點刪去。我們可以在O(nlogn)的時間內求出點集S的凸包V，采用標準的Graham算法即可。設求出的凸包為P1,P2,…Pv，這里的v是求出的凸包上的點數(shù)。P1是所有的點中最低的一個，如果有多個最低的，P1同時還是其中最靠左的一個。P2,P3…Pv按照向量P1Pi與P1P2所成幅角主值從小到大進行排列，而且對于任意1<i<v有向量PiPi+1在向量Pi-1Pi的逆時針方向。這些性質都可以在求凸包的Graham算法中得到保證。凸包求出之后，對每條直線L，一個最簡單的判斷方法就是枚舉凸包的每一點，看它們是否處于L的同一側。但是這種方法的時間復雜度達到O(vm)，最壞情況下是O(nm)，無法接受，因此我們要找到一種高效的判斷方法。首先還是讓我們來深入發(fā)掘一些定義和性質。定義1：凸包V關于向量p的切點Tanpoint(V,p)代表滿足如下性質的一個點：對于凸包上的任意點P，向量Tanpoint-P在向量p的逆時針方向（方向相同或相反也算）。這事實上也就是說，過Tanpoint(V,p)且平行于向量p的直線把凸包上所有的點分在同側（位于直線上的點也看作是同側）。定理2：對于一個凸包V和兩點A、B，設T1=Tanpoint(V,向量AB)，T2=Tanpoint(V，向量BA)，過T1作直線AB的平行線L1，過T2作直線AB的平行線L2，則凸包V上所有的點位于L1、L2中間的帶狀區(qū)域內。證明：根據(jù)定義1，以T1為起點作向量Vec1平行于向量AB，則V中的任意點P滿足向量T1-P在Vec1的逆時針方向，于是V中的點只能位于Vec1的逆時針方向的半平面內。同理，以T2為起點作向量Vec2平行于向量BA，則V中的點只能位于Vec2的逆時針方向的半平面內。所以V中的點可能所在的區(qū)域是Vec1和Vec2各自逆時針方向的半平面的交。由于Vec1和Vec2是反向量，所以這兩個半平面的延伸方向相反，而T2（屬于V中的點）在Vec1的逆時針方向，所以這兩個半平面的交也就是直線L1和L2之間的帶狀區(qū)域。定理3：對于一個凸包V和兩點A、B，設T1=Tanpoint(V,向量AB)，T2=Tanpoint(V，向量BA)，則直線AB穿過凸包的充要條件是T1和T2位于AB的異側。證明：充分性易證：若T1和T2位于AB的異側，則AB至少把T1、T2分在了不同的半平面，所以一定穿過凸包。必要性：假設T1,T2位于直線AB的同側，然而直線AB卻穿過了凸包。根據(jù)定理2，V中所有的點都位于L1和L2之間的帶狀區(qū)域內（L1,L2定義同定理2），直線AB既然穿過了V，那么它必然也穿過這個帶狀區(qū)域，又因為T1,T2位于直線的同側，所以直線AB和線段T1-T2要么沒有交點，要么交點在T1或T2上。但是注意到直線AB平行于L1和L2，不可能過T1或T2，所以AB和線段T1-T2無交點，但是如果直線AB能夠在帶狀區(qū)域內無限延伸，則會和線段T1-T2相交（因為T1-T2把帶狀區(qū)域隔成了兩半），這說明直線AB在帶狀區(qū)域內的長度有限，也就是直線AB會和區(qū)域的邊界——L1、L2相交，這和AB、L1、L2彼此平行相矛盾。所以在若直線AB穿過凸包V，則T1和T2必定在AB異側。根據(jù)定理3，我們又可以把問題轉化成：對于每條給定直線上的兩個點A、B，求出T1=Tanpoint(V,向量AB)和T2=Tanpoint(V,向量BA)，然后判斷T1,T2是否在直線AB的同側。問題的核心是對于凸包V和向量p，如何高效地求出Tanpoint(V,p)。定理4：對于向量p，凸包V中滿足如下性質的點Pi是一個Tanpoint(V,p)：點PiPi+1的與向量P1P2所成幅角的主值AnI大于等于向量p與向量P1P2所成幅角的主值AnP，并且不存在另外一個Pj使PjPj+1與P1P2所成的幅角主值AnJ滿足AnP<=AnJ<AnI。其中點的序號就是它在Graham算法執(zhí)行之后在凸包中的序號，并規(guī)定Pv+1=P1，Pv+2=P2，向量Pv+1Pv+2與向量P1P2所成幅角的主值為2π。也就是說，Pi是使AnI大于等于AnP而且取到盡量?。ㄒ簿褪潜M量接近AnP）的一個點。證明：分情況討論：當i=1時，由于PiPi+1和P1P2所成幅角為0，又大于等于向量p與P1P2所成幅角的主值，說明向量p與P1P2所成幅角也為0，即以Pi為起點作平行于向量p的向量重合于凸包的邊P1P2且方向相同，顯然Pi是Tanpoint。當i=v+1時（此時Pi等于P1），AnI等于2π，又AnP僅僅小于等于AnI，也就是說任何其他的邊與P1P2所成幅角主值都小于AnP。凸包上任意的Pj點和P1構成的向量P1Pj中，與P1P2所成幅角最小的是P1P2，最大的是P1Pv，其中P1P2=Pv+1Pv+2，毫無疑問在向量p的逆時針方向，而P1Pv也只能在p的逆時針方向，因為否則的話，說明PvPv+1在向量p的逆時針方向，而且PvPv+1沒有轉得超過P1P2，說明PvPv+1所與P1P2所成幅角不小于p與P1P2所成幅角，這和AnP僅僅小于等于AnI相矛盾。由于其他的P1Pj都在P1P2和P1Pv之內，P1P2和P1Pv之間轉角不超過π,所以不難得知所有的點Pj都滿足PiPj在向量p的逆時針方向，也即Pi是Tanpoint。當1<i≤v時，假設某個點Pj使得PiPj在向量p的順時針方向。那么我們從Pi出發(fā)，順著凸包的有向邊依次到達下一個頂點，一直到達Pj，此時Pj位于從Pi出發(fā)的向量p的順時針半平面內。從Pj開始繼續(xù)順著凸包有向邊依次到達下一個頂點，總會回到向量p的逆時針半平面內（把Pi看作在逆時針半平面），因為凸包是封閉的圖形。如果在到達Pi之前，到了逆時針半平面內的另一個點Pi'，則說明凸包自交（因為我們訪問點都是按順序的，逆時針半平面內的任何點在Pi之后），這是不可能的，所以總會存在一個Pk點在順時針半平面內，然后從Pk點回到Pi點，而這個Pk點一定是凸包上Pi的前一個點Pi-1（因為i>1）。向量Pi-1Pi與P1P2所成幅角主值小于PiPi+1與P1P2所成幅角主值。又因為PiPi-1在p的順時針方向，所以Pi-1Pi在p的逆時針方向，又向量p與P1P2所成幅角主值AnP小于等于PiPi+1與P1P2所成幅角AnI，所以Pi-1Pi與向量p之間的劣弧范圍內不會夾著向量P1P2，因此向量Pi-1Pi與P1P2所成幅角主值AnJ不小于AnP，也就是存在AnP≤AnJ<AnI，這與題設矛盾。因此，滿足題設的點Pi一定是凸包V關于向量p的切點Tanpoint(V,p)。這樣，求切點的問題又轉化為：在凸包V中求一條有向邊PiPi+1使PiPi+1與P1P2所成幅角AnI不小于p與P1P2所成幅角AnP，而且使AnI盡量小。這樣的PiPi+1是可以采用二分法求出的：定理5：凸包上所有的有向邊P1P2,P2P3,…,PiPi+1,…PvPv+1,Pv+1Pv+2一定按照與向量P1P2所成幅角的主值從小到大進行排列。其中Pv+1=P1,Pv+2=P2且規(guī)定Pv+1Pv+2與P1P2所成幅角主值為2π。簡證：第一條有向邊P1P2與向量P1P2所成幅角為0，一定最小，最后一條有向邊Pv+1Pv+2與P1P2所成幅角為2π，一定最大。對任意1<i≤v，PiPi+1一定在Pi-1Pi的逆時針方向，而且Pi-1Pi所在的方向轉動到PiPi+1所在的方向過程中一定不會越過P1P2，所以每個PiPi+1與P1P2所成的幅角主值大于Pi-1Pi與P1P2所成的幅角主值。也就是這些有向邊與P1P2所成幅角主值依次遞增。定理6：對一個向量p，可以在O(logv)時間內求出有向邊PiPi+1使PiPi+1與P1P2所成幅角AnI不小于p與P1P2所成幅角AnP，而且AnI盡量小。證明：首先我們有P1P2,P2P3,…PiPi+1,…PvPv+1,Pv+1Pv+2這v+1條有向邊，而且它們與P1P2所成幅角依次遞增。因此我們采用二分：維護兩個指針st和ed代表我們想在PstPst+1到PedPed+1這些有向邊內求出一個使AnI不小于AnP而又盡量小的有向邊PiPi+1，其中st≤i≤ed。一個點TanPt代表我們當前求出的最小符合要求的有向邊的起點（也就是當前求得的可能是切點的點）。然后提出算法1：STEP1st,ed分別初始化為1和v+1。STEP2令mid=(st+ed)div2，判斷PmidPmid+1與P1P2所成的幅角AnM是否小于向量p與P1P2所成的幅角AnP。CASE2.1若AnM<AnP，則說明從PstPst+1到PmidPmid+1這些有向邊都不符合要求，于是令st=mid+1，在Pmid+1Pmid+2到PedPed+1這些有向邊中尋找。CASE2.2若AnM≥AnP，則更新TanPt為Pmid，之后若想找到使AnI更小的有向邊，只能在PstPst+1到Pmid-1Pmid這些有向邊里面找了，所以令ed=mid-1。STEP3若st>ed，說明沒有待判斷的有向邊了，TanPt就是所求的有向邊的起點，算法結束；否則還要繼續(xù)判斷，轉STEP2。算法1的正確性顯而易見：其中需要解釋的是CASE2.2中為什么可以直接更新TanPt，這是因為任何時刻只要找到一個Pi使AnI≥AnP，則這個AnI一定大于以前找到的（若以前曾經(jīng)找到過），因為若以前找到了某個有向邊PjPj+1與P1P2所成幅角AnJ≥AnP，以后尋找有向邊PiPi+1就是在PjPj+1邊之前。而這個算法不會遺漏真正最小的AnI也是不難證明的。而算法1的復雜度是O(logv)，因為每次STEP2中，如果進入CASE2.1，那么st=mid+1,ed-st的值減少了(mid+1)-st=(ed-st)div2+1，如果進入CASE2.2，那么ed=mid-1，ed-st的值減少了ed-(mid-1)=(ed-st+1)div2+1。也就是，每步STEP2可以把ed-st的值減少一半以上，而當ed-st=0時，因為STEP2至少將ed-st減少1，所以下一步會將ed-st變成負值，算法結束。因此STEP2執(zhí)行次數(shù)不超過log(ed-st)+1，其中ed和st是初始時的值，分別為v+1和1，所以STEP2的執(zhí)行次數(shù)為O(logv)。而一步STEP2的時間為常數(shù)級，每次STEP2之后才會有STEP3（每步執(zhí)行時間也是常數(shù)級），因此STEP2,3的時間復雜度為O(logv)。而STEP1的時間復雜度顯然為常數(shù)級。綜上所述，算法1可以在O(logv)的時間內求出一條有向邊PiPi+1使向量PiPi+1與P1P2所成幅角AnI在不小于AnP（向量p與P1P2所成幅角）的前提下盡量小，定理6得證。同時根據(jù)定理4，求出的Pi也就是Tanpoint(V,p)。定理7：給出凸包V以及一條直線上的兩點A、B，可以在O(logv)時間內判斷出直線AB是否穿過凸包。證明：根據(jù)定理6，首先兩次執(zhí)行算法1，可以在O(2logv)=O(logv)時間內求出T1=Tanpoint(V,向量AB)和T2=Tanpoint(V,向量BA)。根據(jù)定理3，直線AB穿過凸包V的充要條件是T1和T2在直線AB的兩側。這顯然可以在O(1)的時間內判斷出來。因此，整個判斷的時間就是O(logv)，定理7得證。定理7的證明實際上就給出了判斷一條直線是否穿過凸包V的高效方法，根據(jù)定理1，這事實上也就判斷出了直線是否把點集S中的點分在了兩個不同的半平面。因此，對