几何 - Page 4 - hzwer.com

「BZOJ1069」[SCOI2007] 最大土地面积
Description在某块平面土地上有N个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成的多边形面积最大。Input第1行一个正整数N，接下来N行，每行2个数x,y，表示该点的横坐标和纵坐标。Output最大的多边形面积，答案精确到小数点后3位。SampleInput5001011010.50.5SampleOutput1.000HINT数据范围n<=2000,|x|,|y|<=100000题解n=2000。。。所以可以枚举一条对角线然后在两边分别找一个...
12014年9月3日6,633凸包,旋转卡壳

「BZOJ3707」「FJ2014集训」圈地
「题目描述」2维平面上有n个木桩，黄学长有一次圈地的机会并得到圈到的土地，为了体现他的高风亮节，他要使他圈到的土地面积尽量小。圈地需要圈一个至少3个点的多边形，多边形的顶点就是一个木桩，圈得的土地就是这个多边形内部的土地。（因为黄学长非常的神，所以他允许圈出的第n点共线，那样面积算0）「输入格式」第一行一个整数n，表示木桩个数。接下来n行，每行2个整数表示一个木桩的坐标，坐标两两不同。「输出格式」仅一行，...
32014年8月31日6,222几何,随机化
「FJ2014集训」信心题
「题目描述」在二维平面上有若干个多边形，每个多边形都覆盖了一定的区域，它们之间有可能重叠，请求出这些多边形遮住了多大的平面区域。即，求多边形的面积并。「输入格式」本题为提交答案题，共有10个输入，分别是cover1.in∼cover10.in。每个文件第一行，一个整数，表示这个输入文件的序号(1∼10)。接下来一行，一个整数n，表示这组数据中有n个多边形。接下来n行，每行第一个整数Pi，表示这个多边形有Pi个点，接下来有Pi组整...
02014年7月20日3,511线段树,几何
「NOIP模拟赛」超电磁炮
「题目描述」早苗入手了最新的超电磁炮。最新款自然有着与以往不同的功能，那就是它的轨迹是条直线，厉害吧。2维平面上有n个目标，任意2个目标的坐标不会相同。超电磁炮的威力强到穿透一切，那么早苗一枪最多能击中多少目标？「输入格式」第1行：一个整数n，表示目标数量。第2-n+1行：每行有两个整数xi和yi(-2000000000≤xi，yi≤2000000000)，表示第i个教徒在地图中的行、列坐标。「输出格式」一个整数表示答案。&nbs...
02014年6月27日3,146几何
「BZOJ2391」Cirno的忧郁
DescriptionCirno闲着无事的时候喜欢冰冻青蛙。Cirno每次从雾之湖中固定的n个结点中选出一些点构成一个简单多边形，Cirno运用自己的能力能将此多边形内所有青蛙冰冻。雾之湖生活着m只青蛙,青蛙有大有小，所以每只青蛙的价值为一个不大于10000的正整数。Cirno很想知道每次冻住的青蛙的价值总和。因为智商有限，Cirno将这个问题交给完美算术教室里的你。因为爱护动物，所以每次冻结的青蛙会被放生。也就是说一只青蛙可以被多次...
02014年6月13日5,464treap,几何
「JoyOI1360」Imperishable Shooting
背景Background如果您不想看这个扯淡的背景，可以直接移步Hint，有简洁版。。。一天，蓬莱の魚の形误闯了迷途森林，于是光荣地迷路了。。此时，一个白发红眼的少女出现了。。少女：你迷路了吗？蓬莱の魚の形：。。是。。少女：你叫什么名字？蓬莱の魚の形：蓬莱の魚の形。。少女（仔细打量其一番）：本来还准备帮你的，但是一想到一个妖怪鱼有这个名字。。。就让我看看你有多大本事吧！（突然从背后扇动出熊熊燃烧的翅膀）「Imp...
02014年5月25日5,149treap,几何
「POJ1265」Area
DescriptionBeingwellknownforitshighlyinnovativeproducts,Merckwoulddefinitelybeagoodtargetforindustrialespionage.Toprotectitsbrand-newresearchanddevelopmentfacilitythecompanyhasinstalledthelatestsystemofsurveillancerobotspatrollingthearea.Theserobotsmovealongthewallsofthefacilityandreportsuspiciousobservationstothecentralsecurityoffice.Theonlyflawinthesystemacompetitor抯agentcouldfindisthefac...
02014年4月14日3,715几何
「POJ2954」Triangle
DescriptionA latticepoint isanorderedpair(x, y)where x and y arebothintegers.Giventhecoordinatesoftheverticesofatriangle(whichhappentobelatticepoints),youaretocountthenumberoflatticepointswhichliecompletelyinsideofthetriangle(pointsontheedgesorverticesofthetriangledonotcount).InputTheinputtestfilewillcontainmultipletestcases.Eachinputtestcaseconsistsofsixintegers x1, y1, x2, y2, ...
02014年4月14日3,155几何
「POJ1654」Area
DescriptionYouaregoingtocomputetheareaofaspecialkindofpolygon.Onevertexofthepolygonistheoriginoftheorthogonalcoordinatesystem.Fromthisvertex,youmaygostepbysteptothefollowingvertexesofthepolygonuntilbacktotheinitialvertex.ForeachstepyoumaygoNorth,West,SouthorEastwithsteplengthof1unit,orgoNorthwest,Northeast,SouthwestorSoutheastwithsteplengthofsquarerootof2.Forexample,thisisalegalpolyg...
02014年4月14日2,637几何
「POJ1039」Pipe
DescriptionTheGXLightPipelineCompanystartedtopreparebentpipesforthenewtransgalacticlightpipeline.Duringthedesignphaseofthenewpipeshapethecompanyranintotheproblemofdetermininghowfarthelightcanreachinsideeachcomponentofthepipe.Notethatthematerialwhichthepipeismadefromisnottransparentandnotlightreflecting.Eachpipecomponentconsistsofmanystraightpipesconnectedtightlytogether.Fortheprogrammin...
02014年4月14日2,848几何
「POJ2826」An Easy Problem?!
DescriptionIt'srainingoutside.FarmerJohnson'sbullBenwantssomeraintowaterhisflowers.Bennailstwowoodenboardsonthewallofhisbarn.Showninthepicturesbelow,thetwoboardsonthewalljustlookliketwosegmentsontheplane,astheyhavethesamewidth.Yourmissionistocalculatehowmuchrainthesetwoboardscancollect.InputThefirstlinecontainsthenumberoftestcases.Eachtestcaseconsistsof8integersnotexceeding10,000byabsol...
02014年4月14日5,171几何
「POJ1410」Intersection
DescriptionYouaretowriteaprogramthathastodecidewhetheragivenlinesegmentintersectsagivenrectangle.Anexample:line:startpoint:(4,9)endpoint:(11,2)rectangle:left-top:(1,5)right-bottom:(7,1)Figure1:LinesegmentdoesnotintersectrectangleThelineissaidtointersecttherectangleifthelineandtherectanglehaveatleastonepointincommon.Therectangleconsistsoffourstraightlinesandtheareainbetween.Althoughallinput...
02014年4月13日3,615几何