给定二维平面上的 $n$ 个点,添加一个新点,使得在这 $n+1$ 个点的凸包的边界上的旧点数量最少,且新点必须在凸包上。$n\le 10^5$
在初始的 $n$ 个点的凸包上旋转卡壳,答案即为两个对踵点之间点的数量的最小值。但不好处理存在多点共线的情况。
先在求出保留在边界上的点的凸包,给点编号后,再求出新的凸包。同时在旋转卡壳的时候避免对边平行的情况即可。
给一个边数为 $n$ 的凸多边形和一个半径为 $r$ 的圆,可以平移圆。求两个图形的面积交的最大值。$n\le 10$,$r\le 100$
在 x,y 方向上三分圆心的坐标即可。
一些写的时候的细节:
一般三分要满足极值两侧严格单调,但是这里有很多 (x,y) 对应的面积交都是 $0$ 。采用的实现是,三分 x 时,边界取多边形 x 坐标的最大/最小值;三分 y 时,边界取使面积交不为 $0$ 的 y 的最大/最小值。
之后求多边形和圆面积交。一开始用几何法手写了一个,有几种情况一直不能过。之后上了 Simpson 积分。遇到同样的问题,如果有很多 x 对应的覆盖长度 $f(x)$ 为 $0$ 的话,Simpson 积分会直接退出并返回 $0$ 。解决方案是,先求出多边形和圆的交点,在相邻的交点之间分别做 Simpson 积分。
写好之后跑了大概 4000 ms ,大概几何法时间上会快一些。
补一下多边形和圆交的模板 POJ2986 POJ3675
给平面上 $n$ 条直线,问在平面上划分出了多少个多边形,并求出面积。$n\le1000$
交点最多有 $n\times (n-1)$ 个,因此可以求出所有交点,之后寻找多边形。
交点将直线分为线段,一条线段最多在出现在 $2$ 个多边形上。在线段的两个端点上连双向边。在图上进行 DFS ,访问每一条边,选取下一个点时,总是选取偏转角度最大的,当得到环时计算面积。
然后被求直线交点的精度问题卡了 ~3 个小时。
给二维平面上 $n$ 个点,问有多少四元组满足,一个点在另三个点围成的三角形内。不允许三点共线。$n\le 1000$,$\vert x\vert,\vert y\vert \le 10^9$。