集訓(xùn)隊(duì)作業(yè)dwarfs解題報(bào)告

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