资源描述：
《三分查找技术》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、【标准化说明】三分查找技术与简单应用三分查找技术适用于答案在某一个区间内，这个区间的特点的是，以答案为分点的两侧区间都单调的增大或者减小：如右图就是一个分的例子：三分的区间为[l,r]其中最低点为答案每次把区间分为3个等分取x1=l+(r-l)/3,x2=r-(r-l)/3作为分点，看谁更接近标准答案，并以此来更新左右区间，继续进行二分，直到得到(无限逼近)答案。TrickorTreatDescriptionJohnnyandhisfriendshavedecidedtospendHalloweennightdoingtheusua
2、lcandycollectionfromthehouseholdsoftheirvillage.Asthevillageistoobigforasinglegrouptocollectthecandyfromallhousessequentially,Johnnyandhisfriendshavedecidedtosplitupsothateachofthemgoestoadifferenthouse,collectsthecandy(orwreakshavociftheresidentsdon'tgiveoutcandy),and
3、returnstoameetingpointarrangedinadvance.Therearenhousesinthevillage,thepositionsofwhichcanbeidentifiedwiththeirCartesiancoordinatesontheEuclideanplane.Johnny'sgangisalsomadeupofnpeople(includingJohnnyhimself).Theyhavedecidedtodistributethecandyaftereverybodycomesbackwi
4、ththeirbooty.Thehousesmightbefaraway,butJohnny'sinterestisineatingthecandyassoonaspossible.Keepinginmindthat,becauseoftheirresponsetothehospitalityofsomevillagers,somechildrenmightbewantedbythelocalauthorities,theyhaveagreedtofixthemeetingpointbytheriverrunningthrought
5、hevillage,whichistheliney=0.Notethattheremaybehousesonbothsidesoftheriver,andsomeofthehousesmaybehouseboats(y=0).Thewalkingspeedofeverychildis1meterpersecond,andtheycanmovealonganydirectionontheplane.Atexactlymidnight,eachchildwillknockonthedoorofthehousehehaschosen,co
6、llectthecandyinstantaneously,andwalkbackalongtheshortestroutetothemeetingpoint.TellJohnnyatwhattimehewillbeabletostarteatingthecandy.InputEachtestcasestartswithalineindicatingthenumbernofhouses(1n50000).Thenextnlinesdescribethepositionsofthehouses;eachoftheselinesconta
7、instwofloatingpointnumbersxandy(-200000x,y200000),thecoordinatesofahouseinmeters.Allhousesareatdifferentpositions.Ablanklinefollowseachcase.Alinewithn=0indicatestheendoftheinput;donotwriteanyoutputforthiscase.OutputForeachtestcase,printtwonumbersinalineseparatedbyaspac
8、e:thecoordinatexofthemeetingpointontheliney=0thatminimizesthetimethelastchildarrives,andthistimeitself(measuredinseco
