CVBB ACM Team

--- 2020-2021:teams:i_dont_know_png:qxforever:geometryproblems [2020/06/29 04:44]
qxforever 创建
+++ 2020-2021:teams:i_dont_know_png:qxforever:geometryproblems [2020/06/29 07:54] (当前版本)
qxforever [解题思路]
@@ 行 50: / 行 50: @@
 然后被求直线交点的精度问题卡了 ~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]] 踩过坑了这里就没踩。