• 「想法题系列」逗比三角形

    「想法题系列」逗比三角形

    「题目描述」小J是一名OI退役滚粗文化课选手,他十分喜欢做题,尤其是裸题。他现在有一个二维盒子和一些二维三角形,这个盒子拥有无限的高度和L的宽度。而且他的三角形也都是一些锐角三角形或者是直角三角形。现在小J想把这些三角形放入盒子里,由于小J从txt大神犇那里学会了魔♂法,所以小J的三角形既可以无视盒子边界又可以重叠放置,但是必须有一条边紧贴盒子底面所在的直线。现在小J想要最大化在盒子中的被三角形覆盖的...

    02014年10月29日1,526二分法,几何
  • 「BZOJ2618」[CQOI2006] 凸多边形

    「BZOJ2618」[CQOI2006] 凸多边形

    Description逆时针给出n个凸多边形的顶点坐标,求它们交的面积。例如n=2时,两个凸多边形如下图:则相交部分的面积为5.233。Input第一行有一个整数n,表示凸多边形的个数,以下依次描述各个多边形。第i个多边形的第一行包含一个整数mi,表示多边形的边数,以下mi行每行两个整数,逆时针给出各个顶点的坐标。 Output输出文件仅包含一个实数,表示相交部分的面积,保留三位小数。 SampleInput26-20-1-21-22012-1240-3...

    12014年10月16日2,977半平面交
  • 「BZOJ1038」[ZJOI2008] 瞭望塔

    「BZOJ1038」[ZJOI2008] 瞭望塔

    Description致力于建设全国示范和谐小村庄的H村村长dadzhi,决定在村中建立一个瞭望塔,以此加强村中的治安。我们将H村抽象为一维的轮廓。如下图所示我们可以用一条山的上方轮廓折线(x1,y1),(x2,y2),….(xn,yn)来描述H村的形状,这里x1<x2<…<xn。瞭望塔可以建造在[x1,xn]间的任意位置,但必须满足从瞭望塔的顶端可以看到H村的任意位置。可见在不同的位置建造瞭望塔,所需要建造的高度是不同的。为了节省开支,dadzhi...

    82014年10月16日3,480半平面交
  • 「BZOJ1132」[POI2008] Tro

    「BZOJ1132」[POI2008] Tro

    Description平面上有N个点.求出所有以这N个点为顶点的三角形的面积和N<=3000Input第一行给出数字N,N在[3,3000]下面N行给出N个点的坐标,其值在[0,10000]Output保留一位小数,误差不超过0.1SampleInput50012021011SampleOutput7.0题解叉积求面积:abs(xi*yj-yi*xj)所以去掉绝对值,把xi和xj提出来就可以求和了每次把最左边的点当成原点,然后剩下的极角排序,接着枚举第二个点,求叉积之和……坐标都是整数,用lon...

    02014年10月11日1,844几何
  • 「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日2,499半平面交
  • 「FJOI2013」圆形游戏

    「FJOI2013」圆形游戏

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

    42014年9月23日2,672几何,博弈论
  • 「POJ2932」Coneology

    「POJ2932」Coneology

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

    02014年9月23日1,437几何
  • 「BZOJ1670」[Usaco2006 Oct] Building the Moat护城河的挖掘

    「BZOJ1670」[Usaco2006 Oct] Building the Moat护城河的挖掘

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

    02014年9月13日2,106凸包
  • 「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日3,869凸包,旋转卡壳
  • 「BZOJ3707」「FJ2014集训」圈地

    「BZOJ3707」「FJ2014集训」圈地

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

    32014年8月31日2,481几何,随机化
  • 「FJ2014集训」信心题

    「FJ2014集训」信心题

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

    02014年7月20日1,376线段树,几何
  • 「NOIP模拟赛」超电磁炮

    「NOIP模拟赛」超电磁炮

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

    02014年6月27日1,289几何