• 【poj2451】Uyuw’s Concert

    【poj2451】Uyuw's Concert

    DescriptionPrinceRemmargutssolvedtheCHESSpuzzlesuccessfully.Asanaward,UyuwplannedtoholdaconcertinahugepiazzanamedafteritsgreatdesignerIhsnayish.ThepiazzainUDF-UnitedDeltaofFreedom’sdowntownwasasquareof[0,10000]*[0,10000].Somebasketchairshadbeenstandingthereforyears,butinaterriblemess.Lookatthefollowinggraph.Inthiscasewehavethreechairs,andtheaudiencesfacethedirectionaswhatarro...

    132014年10月4日1,737半平面交
  • 【FJOI2013】圆形游戏

    【FJOI2013】圆形游戏

    题目描述在一个无穷大的桌面上有n个圆形,保证任意2个圆相离或者相含,不存在相切或相交。现在Alice和Bob在玩一个圆形游戏,以Alice为先手,双方以如下步骤轮流游戏:1) 选定一个圆A,把A以及所有完全在A内部的圆都删除;2) 如果在自己回合无法找到可删除的圆,则输掉比赛。假设Alice和Bob都非常聪明,请问最终谁能够取得胜利?请编程输出最终获胜的人。输入输入数据的第一行为一个正整数T,表示数据组数。接下来T组数...

    42014年9月23日1,901几何,博弈论
  • 【poj2932】Coneology

    【poj2932】Coneology

    DescriptionAstudentnamedRoundSquarelovedtoplaywithcones.Hewouldarrangeconeswithdifferentbaseradiiarbitrarilyonthefloorandwouldadmiretheintrinsicbeautyofthearrangement.Thestudentevenbegantheorizingabouthowsomeconesdominateothercones:aconeAdominatesanotherconeBwhenconeBiscompletelywithintheconeA.Furthermore,henotedthattherearesomeconesthatnotonlydominateothers,butarethemselvesdominated,th...

    02014年9月23日1,095几何
  • 【bzoj1670】[Usaco2006 Oct]Building the Moat护城河的挖掘

    【bzoj1670】[Usaco2006 Oct]Building the Moat护城河的挖掘

    Description为了防止口渴的食蚁兽进入他的农场,FarmerJohn决定在他的农场周围挖一条护城河。农场里一共有N(8<=N<=5,000)股泉水,并且,护城河总是笔直地连接在河道上的相邻的两股泉水。护城河必须能保护所有的泉水,也就是说,能包围所有的泉水。泉水一定在护城河的内部,或者恰好在河道上。当然,护城河构成一个封闭的环。挖护城河是一项昂贵的工程,于是,节约的FJ希望护城河的总长度尽量小。请你写个程序计算一下...

    02014年9月13日1,479凸包
  • 【bzoj1069】[SCOI2007]最大土地面积

    【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日2,485凸包,旋转卡壳
  • 【bzoj3707】【FJ2014集训】圈地

    【bzoj3707】【FJ2014集训】圈地

    【题目描述】2维平面上有n个木桩,黄学长有一次圈地的机会并得到圈到的土地,为了体现他的高风亮节,他要使他圈到的土地面积尽量小。圈地需要圈一个至少3个点的多边形,多边形的顶点就是一个木桩,圈得的土地就是这个多边形内部的土地。(因为黄学长非常的神,所以他允许圈出的第n点共线,那样面积算0)【输入格式】第一行一个整数n,表示木桩个数。接下来n行,每行2个整数表示一个木桩的坐标,坐标两两不同。【输出格式】仅一行,...

    32014年8月31日1,734几何,随机化
  • 【FJ2014集训】信心题

    【FJ2014集训】信心题

    【题目描述】在二维平面上有若干个多边形,每个多边形都覆盖了一定的区域,它们之间有可能重叠,请求出这些多边形遮住了多大的平面区域。即,求多边形的面积并。【输入格式】本题为提交答案题,共有10个输入,分别是cover1.in∼cover10.in。每个文件第一行,一个整数,表示这个输入文件的序号(1∼10)。接下来一行,一个整数n,表示这组数据中有n个多边形。接下来n行,每行第一个整数Pi,表示这个多边形有Pi个点,接下来有Pi组整...

    02014年7月20日1,016线段树,几何
  • 【NOIP模拟赛】超电磁炮

    【NOIP模拟赛】超电磁炮

    【题目描述】早苗入手了最新的超电磁炮。最新款自然有着与以往不同的功能,那就是它的轨迹是条直线,厉害吧。2维平面上有n个目标,任意2个目标的坐标不会相同。超电磁炮的威力强到穿透一切,那么早苗一枪最多能击中多少目标? 【输入格式】第1行:一个整数n,表示目标数量。第2-n+1行:每行有两个整数xi和yi(-2000000000≤xi,yi≤2000000000),表示第i个教徒在地图中的行、列坐标。 【输出格式】一个整数表示答案。&nbs...

    02014年6月27日964几何
  • 【bzoj2391】Cirno的忧郁

    【bzoj2391】Cirno的忧郁

    DescriptionCirno闲着无事的时候喜欢冰冻青蛙。Cirno每次从雾之湖中固定的n个结点中选出一些点构成一个简单多边形,Cirno运用自己的能力能将此多边形内所有青蛙冰冻。雾之湖生活着m只青蛙,青蛙有大有小,所以每只青蛙的价值为一个不大于10000的正整数。Cirno很想知道每次冻住的青蛙的价值总和。因为智商有限,Cirno将这个问题交给完美算术教室里的你。因为爱护动物,所以每次冻结的青蛙会被放生。也就是说一只青蛙可以被多次...

    02014年6月13日1,654treap,几何
  • 【tyvj1360】Imperishable Shooting

    【tyvj1360】Imperishable Shooting

    背景Background如果您不想看这个扯淡的背景,可以直接移步Hint,有简洁版。。。一天,蓬莱の魚の形误闯了迷途森林,于是光荣地迷路了。。此时,一个白发红眼的少女出现了。。少女:你迷路了吗?蓬莱の魚の形:。。是。。少女:你叫什么名字?蓬莱の魚の形:蓬莱の魚の形。。少女(仔细打量其一番):本来还准备帮你的,但是一想到一个妖怪鱼有这个名字。。。就让我看看你有多大本事吧!(突然从背后扇动出熊熊燃烧的翅膀)「Imp...

    02014年5月25日1,670treap,几何
  • 【poj1265】Area

    【poj1265】Area

    DescriptionBeingwellknownforitshighlyinnovativeproducts,Merckwoulddefinitelybeagoodtargetforindustrialespionage.Toprotectitsbrand-newresearchanddevelopmentfacilitythecompanyhasinstalledthelatestsystemofsurveillancerobotspatrollingthearea.Theserobotsmovealongthewallsofthefacilityandreportsuspiciousobservationstothecentralsecurityoffice.Theonlyflawinthesystemacompetitor抯agentcouldfindisthefac...

    02014年4月14日1,545几何
  • 【poj2954】Triangle

    【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日1,028几何
  • 【poj1654】Area

    【poj1654】Area

    DescriptionYouaregoingtocomputetheareaofaspecialkindofpolygon.Onevertexofthepolygonistheoriginoftheorthogonalcoordinatesystem.Fromthisvertex,youmaygostepbysteptothefollowingvertexesofthepolygonuntilbacktotheinitialvertex.ForeachstepyoumaygoNorth,West,SouthorEastwithsteplengthof1unit,orgoNorthwest,Northeast,SouthwestorSoutheastwithsteplengthofsquarerootof2.Forexample,thisisalegalpolyg...

    02014年4月14日893几何