2004年16届国际信息学奥赛试题

《2004年16届国际信息学奥赛试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2004年第16届国际信息学奥赛试题解析（希腊）第一题阿耳特弥斯Day1.SourcefileArtemis.*Availablememory:16M.Maximumrunningtime:1SZeusgaveArtemis,thegoddessofthewilderness,arectangularareaforgrowingaforest.Withtheleftsideoftheareaasasegmentofthepositivey-axisandthebottomsideasasegmentofthepositivex-axis,a

2、nd(0,0)theleftbottomcornerofthearea,ZeustoldArtemistoplanttreesonlyonintegercoordinatepointsinthearea.Artemislikedtheforesttolooknatural,andthereforeplantedtreesinsuchawaythatalineconnectingtwotreeswasneverparalleltox-axisory-axis.Attimes,ZeuswantsArtemistocuttreesforhim.T

3、hetreesaretobecutasfollows:1．ZeuswantsatleastagivennumberToftreestobecutforhim.2．Togetarectangularfootballpitchforfuturefootballsuccess,Artemisistocutalltreeswithinarectangulararea,andnotreesoutsideofit.3．Thesidesofthisrectangularareaaretobeparalleltox-axisandy-axis.4．Twoo

4、ppositecornersoftheareamustbelocatedontreesandthereforethosecornertreesarealsocut.AsArtemislikesthetrees,shewantstofulfilltheseconditionswhilstcuttingasfewtreesaspossible.Youaretowriteaprogramthat,giveninformationontheforestandtheminimumnumberToftreestobecut,selectsanareaf

5、orcuttingtreesforArtemis.INPUTTheinputfilenameisartemis.in.ThefirstlinecontainsoneintegerN:thenumberoftreesintheforest.ThesecondlinecontainsoneintegerT:theminimumnumberoftreestobecut.ThefollowingNlinesdescribethepositionsoftheNtrees.EachoftheselinescontainstwointegersXandY

6、:thex-coordinatefollowedbythey-coordinateofatree.OUTPUTSTheoutputfilenameisartemis.out.ThefileistocontainonelinewithtwointegersIandJ29separatedbyonespace:ArtemisshouldusetheJthtree(withpositiongivenonline1+2oftheinputfile)andJthtree(withpositiongivenonlineJ+2oftheinputfile

7、)asthecornersoftheareaforcuttingtrees.Theorderofthesetwonumberisirrelevant.Theremaybeseveralwaystochoosethesetreesandyouneedtofindandoutputoneofthem.Foralltestcasesatleastonesolutionexists.EXAMPLEINPUTSANDOUTPUTSartemis.inartemis.out1232112356CONSTRAINSInallinputs,1≤N≤2000

8、0,0≤X,Y≤64000and,1