Ear
作者 : 周子鑫 徐明宽
关键词 : 几何、数学
题目简述
在坐标系上有一些红点和一些蓝点，其中红点都在轴上，蓝点都在轴上方。对于一个由个红点和两个蓝点组成的集合，我们定义它为"Ear"当且仅当它们满足下面的条件：
- 严格在线段内。
- 点在轴上的投影严格在 内，点在轴上的投影严格在内。
- 点严格在三角形内。
（脑补一下这个就是个耳朵，例如下图：
现在给你红点和个蓝点，求总共有多少只"Ear"。
分析
这种类型的题目，首先是要确定固定哪些点。
相对来说和这两个点的限制比较复杂（要求在三角形内），那么就先把两个点先枚举一下。
再枚举一个红点就行了。
那么如何将在三角形这个限制转化为容易计算的限制呢？ 只要向量在向量右侧就行了。
算法一
枚举完三个点之后：
- 点的位置就已经确定下来了，只有可能在投影和之间，而且点的位置不受 影响（因为 两个点都在的投影左侧）
- 接下来考虑点的位置，因为有个限制是在三角形之内，所以点一定在直线与轴交点的左侧。需要注意的是，点还有一个限制就是要在点投影的左侧。
- 接下来的位置就简单了，一定在点和点投影之间。
考虑如何计算答案：
- 点的数目是确定的，可以直接根据和的位置计算出来。时间复杂度
- 随着点的移动，点的可行区间也随之发生变化，的可行区间右端点是已经确定的，而左端点就是的位置。这样就发现，对于不同的, 可行的数量实际上是一个等差数列。时间复杂度
因此总的时间复杂度就是，空间复杂度
算法二
其实这道题中点和点的地位是等价的，那么既然不需要枚举点的位置，不妨也不枚举点的位置试试。即，只枚举两个点，现在我们再来看看都有哪些限制条件。
- 同样地，点在直线与轴交点的左侧，也在点投影的左侧。
- 对称地，点在直线与轴交点的右侧，也在点投影的右侧。
- 点在点和点投影之间。
- 点在点投影和点之间。
同样地，对于不同的，可行的数量仍然是一个等差数列。注意到点的位置和点的位置无关，而且点与点左右对称，所以对于不同的，可行的数量也是一个等差数列。把两个等差数列的和乘起来就得到了答案。
这样总时间复杂度就降低到了。