半平面求交算法

/Sｔep１：Ｓeparatetheh-plａnｅsiｎｔotwosｅtｓ。Onehａspolａrａnglｅsof(-½π，½π]，ｔheｏtherhasthoseof(-π，—½π]∪（½π,π］。将半平面分成两部分,一部分极角范围（－½π，½π],另一部分范围（-π，-½π]∪（½π,π］Ｓtep2：Cｏnsidｅrｔhesetofh－pｌaneｓｉn(—½π，½π］（thｅotheｒsetｓhouldalsｏgoｔhrｏughsｔep3and4simiｌarｌｙ）。Ｓｏｒtthemｂythepoｌaraｎglｅ.Ｆoｒｔheh—pｌａｎeｓwiｔhthesamepoｌaｒａngle，weｃａｎｋｅｅponｌyonｅdｏwn(deｌｅｔｅalｌotｈers）ａccordingtothecoｎstantofｔhesｅh—pｌanｅs考虑（-½π，½π]的半平面(另一个集合类似地做Stｅp3/４），将他们极角排序。对极角相同的半平面，根据常数项保留其中之一。Step3。1：Startｉｎｇｆrｏmtwｏh－ｐlaｎｅsｗiththelｅaｓtpｏlarａngle,coｍputeｔｈｅｉｒiｎtｅｒsection.Pushthｅmtwointoaｓtacｋ.从排序后极角最小两个半平面开始，求出它们的交点并且将他们押入栈.Ｓtep3．2：Eachｔｉme,adｄoｎemoreｈ-planｅｂｙｉncｒeasinｇordｅrofpolarangｌeｓ,andｃalculateｔheｉnterｓｅctioｎｏｆitandtｈetoph-ｐlaneiｎstａck.每次按照极角从小到大顺序增加一个半平面,算出它与栈顶半平面的交点。Sｔｅp３。3：Ｉｆtｈｉsiｎterｓｅｃtioniｓｔotheｒightofthｅintersectioｎｏftoptwoh—planesinsｔａck，weｐｏptheｓtaｃkonｃe.如果当前的交点在栈顶两个半平面交点的右边，出栈（ｐop)。upperupperhull上壳lowerhull下壳Sｔｅp4.1:Ｉｎtｅrｓectionsｏfａdjacenth-planepairsinsｔacｋfoｒmhａlfａｃonvexｐolｙgoｎ。Fｏrｔheｔwｏseｔs，ｗehavetwoｈalｖes–（-½π，½π］givｅsaｎupperｈｕｌｌaｎd（—π,－½π］∪（½π，π]giｖesａlowerｈull.相邻半平面的交点组成半个凸多边形。我们有两个点集,（—½π，½π]给出上半个，（－π,—½π］∪（½π，π］给出下半个p4p4p3p1p2upperhull上壳lowerhull下壳Step４。2：Attｈebeｇiｎniｎｇ，ｆourpoｉnｔersp１,ｐ2,p3andp4inｄicateleｆtmost／riｇｈtmosｔedｇesofbｏthupperａndlowerｈulls。ｐ1anｄp3moverｉｇhｔwards，whiｌｅp2ａndp4walkslｅftｗarｄs．初始时候，四个指针ｐ１,p2,p３ａｎdｐ4指向上/下凸壳的最左最右边p1,p3向右走，p２,ｐ4向左走p3p3p4p1p2Steｐ4.3：Ａtanyｔimｅ,iｆthｅｌｅftmoｓｔｉntersectｉonｉｓagainｓｔthｅfeasiｂlｅregionｐrovｉdedｂyp１oｒp3,ｗｅareｓｕretheｌeftmoｓtoneistobｅreｍoved.Naturalｌy，ｐ1oｒp3walksriｇhtwardsｔoitｓadjaceｎtedgｅ．任意时刻,如果最左边的交点不满足ｐ１/p3所在半平面的限制，我们相信这个交点需要删除p１或p3走向它右边的相邻边p3p3p2p1p4p3p4p2p1Thejｕdgmenthｏlｄsanaｌogouslｙｆorrightmostinｔersecｔionwitｈp２ａｎdp4。类似地我们处理最右边的交点p3p3p4p2p1Stｅp4。4:Ｄothｅabｏveremovingrepeａteｄｌyｕntilｔhｅreiｓnｏmoｒeupdatｅ.重复运作直到不再有更新出现—-迭代Everythingexceptsorting(Sｔep２)iｎS＆Ialｇorithｍrｅmainlｉｎｅａr–O(n）runninｇｔime。Usuallyｗeusｅquｉck—soｒt.TｈetotalcoｍplexitｙisO（ｎｌoｇｎ）,wｉthfａirlｙsmａllconstａntｆactorｈｉdden.除了Step2中的排序以外,S＆I算法的每一步都是线性的。通常我们用快速排序实现Steｐ2，总的时间复杂度为O(nloｇn)，隐蔽其中的常数因子很小简单地说,我保存每一条直线的起点与终点，然后规定该(有向）直线的左手侧为半平面内部。这样，判断点是否在半平面内，还有极角序的工作变得相当简单,但是求交点就尴尬了。(求交点的精妙之处在于两个叉积的正负符号可以不同)ﻫ（这是极角序和判断点在平面内外的图示。被排序半平面平行的时候，比如图中的AD和ＢＣ，如果BＤ在AC的左手方向，那就应该保留ＡＤ，这个可以用叉积判断。判断点在平面内外时，点在半平面外＜＝〉点在半平面右手侧。）Ｃodｅ(POJ245１）://suｂmititbyC+＋iｎsteadofG＋＋

#iｎｃlude<ｃstdio〉

＃incｌude＜cmatｈ〉

#includｅ＜ａlgorｉthm〉ﻫuｓingnamｅspacestｄ；ﻫﻫ#ｄeｆineMXN20０５０

cｏｎstdouｂｌeeｐｓ=1e－7；ﻫinlｉｎｅiｎtsgｎ（doｕblea）{

if（fａbs(ａ)<eｐs）retuｒn０；ﻫrｅturn（a〈0）?-１：1;ﻫ}ﻫ#dｅｆineZERＯ(X)(sgn(X)==0)

#defｉｎｅNＥGＡ（X)(sｇn（X)==－１）

#definｅＰOＳI(X)（sgn(X）==1）ﻫ

ｓtruｃtｐｏinｔ{

doublex，y;ﻫｐｏinｔ()：x（０)，y（0){｝ﻫｐｏiｎt(ｄoublea,ｄoubｌｅb)：x(a),y（b）｛｝

poｉntoｐeratｏr—(conｓtpoint＆b）const｛

returnpoiｎt（x－b.x,y—b.y);ﻫ｝

dｏｕblｅｏpeｒaｔor＊（ｃonstpoint&b)conｓt｛ﻫｒｅｔurnx＊b.y—ｙ＊b．x；

｝

booｌoperａｔｏr＝=(ｃｏｎsｔpｏｉｎt＆b)ｃonｓt{ﻫreturn(ZERO（y—ｂ.y）&＆ZERO（x—b。ｘ）)；

}ﻫ}Ｐ[MＸN]；

ﻫｓtructhvｅc{ﻫpoiｎｔs，t；ﻫdoubleang；

pointｏpｅratoｒ*(cｏnｓｔhvec＆b)ｃonst｛ﻫdｏｕｂleｓ１=(b.t-ｓ)＊（ｂ.s-s),

s2=（b。s—t）*(b。ｔ—t）；

ｒetｕrnpｏint(（s。x＊s2+t.x*ｓ１）／（ｓ2＋s１），ﻫ(s.y*s２+t。y＊s1)/（ｓ2＋ｓ１））；

｝ﻫboolopｅrａtｏr<（cｏnsthveｃ＆ｂ）ｃｏｎst{

if(ZＥRO（b.anｇ－ａng））

reｔｕrnｓgn（(b.t-b.ｓ）＊（t-ｂ.ｓ）)＞=０;ﻫｅｌｓｅｒｅtuｒnanｇ〈b.ang；

}

｝H［ＭＸN］，Q［MXＮ］;

iｎtN;ﻫﻫinlinebｏｏlisouｔ（ｃonｓthveｃ＆h,ｃonｓtpoint&ｐ){

ｒetuｒｎPOSI（（p—h.s）*(ｈ.ｔ-h．s））；ﻫ}

ｉnlｉｎｅboolｐａrralｅｌ(constｈｖec＆a,conｓthvec＆b）｛ﻫretｕrnＺERO(（a．ｔ－a。s)＊（b.t－b．s））；ﻫ｝

pｏintｉnｔe（ｈveca，ｈvecb)｛rｅtｕrna＊b；｝

boolleｓstahn（hveca,ｈvecｂ）｛rｅｔｕｒｎａ＜ｂ；}

ﻫｉnlｉneinthveｃ_int（)｛

ｉntＭ＝0,C＝1，ｌ=0，r=1；

ｓort（Ｈ+1，Ｈ+N+1）;

for（iｎｔi=2；i〈=N；++i）

if（!ＺERＯ(H[i］．ang－Ｈ［i—１].ang)）

H[＋＋Ｃ］＝Ｈ[ｉ］；ﻫQ［0]=H［１］，Q[1］=Ｈ[2］；

for（inti=３;i〈=Ｃ;++i）｛

while(l〈ｒ&＆ｉsｏut（H［i],Q［r]*Q[r—1]））-—r;ﻫwhile（l＜r＆&iｓout(H[i]，Ｑ[l］＊Q［l+1］)）＋＋ｌ;ﻫQ［＋+r］＝H[i］;

}

wｈile(l<r&＆isout（Ｑ［ｌ],Q[ｒ］*Q[ｒ-１］）)-—r；ﻫwhｉle（l〈r&＆ｉsoｕt(Q［ｒ]，Ｑ［l]＊Q［l+1］）)＋+l;ﻫｉｆ（r＜=ｌ+1)retｕrn0；

for(intｉ=ｌ;i〈r;++i）P[++M］=Q［i］＊Ｑ[i+1］；

P［++M]＝Q［l]*Q[r]；ﻫＭ=ｕnique(P＋１，Ｐ+M+１)—P—1;ﻫｒetｕrnM;ﻫ｝

ｄoｕbleaｒｅa(intｎ）{ﻫif（ｎ＜３)return０；

doubles＝０;ﻫfｏr（inti=1;ｉ<=ｎ；++i)ﻫs+＝Ｐ[i］*Ｐ［ｉ%n＋1］；

retｕrnfabs（s／2）；ﻫ}

voidadｄ_ｈｖec（points,ｐoinｔt）{

H[++N].s＝s，H[N]。ｔ=t；

ｐoｉｎtｃ=ｔ-s;

Ｈ［N］．ang=atan2（c.ｙ,c。x)；

}ﻫﻫinｔmain（）{ﻫintm;

＃ifｄｅｆLOCＡLﻫｆｒeｏpen（"uｙuｗ．in”,"ｒ",sｔdin）；

#endifﻫＮ=0;ﻫａdd＿hvec(ｐoint(0,0),poｉnt(１000０，0）），

add_hveｃ（point（１000０，0)，poinｔ（１０00０,10000）），

ａdd_hvｅc（poiｎt(10000，1000０)，poiｎt(０，10000)）,ﻫaｄd_hvec(ｐｏinｔ（0,1000０），point（０，