1 条题解
-
0
题目分析
题意回顾
在一个圆上,逆时针等距分布着 个点,我们放置一些关键点,当一个以关键点为三个顶点的非退化三角形且内部包含原点时称其为好三角形,统计所有好三角形的个数。
分析
正难则反。
我们尝试统计内部不包含原点的三角形,再用任选出三个点的总数减去。
我们发现当一个三角形在圆的半径的一边时,一定为不合法,否则为合法。
我们假设一条直线为圆的半径,每次统计出以 为顶点之一且剩下的顶点都在以直线为分割,与 同侧的半圆中的三角形个数,要维护当前半圆内的点数总和,再将直线旋转一格。
注意 c 奇偶的分类讨论,以及
long long的使用。
- 1
信息
- ID
- 169
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者