• 2017ACM萧山训练第5场(2016 Pacific Northwest – Division 1)

    2017ACM萧山训练第5场(2016 Pacific Northwest - Division 1)

    E.Enclosure做出大小两个凸包,即所有点的凸包和前k个点的凸包按动态凸包的思路,新加入的点会把小凸包上连续的一些点弹出,这些点是一个连续的区间相当于切掉凸包的一个角,加入一个三角形若在大凸包上顺时针枚举一个加入的点,这个区间左右端点也是顺时针转的,类似旋转卡壳切掉部分的面积顺便维护由于坐标范围较大,用double精度会炸[crayon-65f96f369da3b202598591/]G.MaximumIslandsL的上下左右直接贪心为W然后剩下的就...

  • 「FJ2015集训」签到题

    「FJ2015集训」签到题

    「问题描述」给定一个n个点的严格凸多边形(各个内角<180°),现在要切出两个非退化三角形(三点不共线),要求两个三角形顶点必须是凸多边形的顶点,且三角形不可相交(但是点或边可以重合)。求两个三角形面积之差的最大值。「输入格式」第一行,一个整数N。第二到N+1行,每行两个整数xi,yi,表示多边形的一个点,保证顶点按顺时针或逆时针顺序给出。「输出格式」输出答案,精确到小数点后1位。「样例输入1」400011210「样...

    12015年7月12日3,582旋转卡壳
  • 「POJ2187」Beauty Contest

    「POJ2187」Beauty Contest

    DescriptionBessie,FarmerJohn'sprizecow,hasjustwonfirstplaceinabovinebeautycontest,earningthetitle'MissCowWorld'.Asaresult,BessiewillmakeatourofN(2<=N<=50,000)farmsaroundtheworldinordertospreadgoodwillbetweenfarmersandtheircows.Forsimplicity,theworldwillberepresentedasatwo-dimensionalplane,whereeachfarmislocatedatapairofintegercoordinates(x,y),eachhavingavalueintherange-10,000...1...

    12015年1月25日7,801凸包,旋转卡壳
  • 「BZOJ1185」[HNOI2007] 最小矩形覆盖

    「BZOJ1185」[HNOI2007] 最小矩形覆盖

    Description题解首先有一个结论,矩形的一条边一定在凸包上!!!枚举凸包上的边用旋转卡壳在凸包上找矩形另外三点。。。注意精度问题[crayon-65f96f369f5cc184173799/]  ...

    72014年12月24日7,877凸包,旋转卡壳
  • 「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日6,374凸包,旋转卡壳