===== BUAA Spring Training 14 - B =====

[[https://codeforces.com/gym/101790/problem/B|链接]]

==== 题意 ====

给定二维平面上的 $n$ 个点，添加一个新点，使得在这 $n+1$ 个点的凸包的边界上的旧点数量最少，且新点必须在凸包上。$n\le 10^5$

==== 解题思路 ====

在初始的 $n$ 个点的凸包上旋转卡壳，答案即为两个对踵点之间点的数量的最小值。但不好处理存在多点共线的情况。

先在求出保留在边界上的点的凸包，给点编号后，再求出新的凸包。同时在旋转卡壳的时候避免对边平行的情况即可。

===== BUAA Summer Training 11 - J =====

[[https://codeforces.com/gym/101158/problem/J|链接]]

==== 题意 ====

给一个边数为 $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

===== 2019 牛客暑期多校训练营 2 - G =====

[[https://ac.nowcoder.com/acm/contest/882/G|链接]]

==== 题意 ====

给平面上 $n$ 条直线，问在平面上划分出了多少个多边形，并求出面积。$n\le1000$

==== 解题思路 ====

交点最多有 $n\times (n-1)$ 个，因此可以求出所有交点，之后寻找多边形。

交点将直线分为线段，一条线段最多在出现在 $2$ 个多边形上。在线段的两个端点上连双向边。在图上进行 DFS ，访问每一条边，选取下一个点时，总是选取偏转角度最大的，当得到环时计算面积。

然后被求直线交点的精度问题卡了 ~3 个小时。

===== 2019 牛客暑期多校训练营 8 - F =====

[[https://ac.nowcoder.com/acm/contest/888/F|链接]]

==== 题意 ====

给二维平面上 $n$ 个点，问有多少四元组满足，一个点在另三个点围成的三角形内。不允许三点共线。$n\le 1000$，$\vert x\vert,\vert y\vert \le 10^9$。

==== 解题思路 ====

除了共线需要额外处理之外，基本算是 [[https://codeforces.com/contest/1284/problem/E|CF1284E]] 的弱化版。

枚举被围的点作为中心点，极角排序。考虑从所有可能方案即 $\binom{n-1}{3}$ 中减去不合法的方案。

一个方案需要三个点。按极角序枚举点，计算该点做为三角形中极角序最小的点的且不合法的方案数。对于剩下两个点的位置，当另两个点位于中心点与枚举的点的同侧时，中心点落在三角形外。''%%lower_bound%%'' 找一下范围即可。

共线不难处理，注意不要重复计算一些非法情况。时间复杂度 $O(n^2\log n)$

$10^9$ 的坐标范围下，使用 ''%%atan2%%'' 进行极角排序大概率会有精度问题。在 [[https://codeforces.com/contest/1284/problem/E|CF1284E]] 踩过坑了这里就没踩。