偷懒用了 zhoutb2333 的简单做法(
很好写啊(
首先有一个结论:平面上 n 个不同点组成的等腰三角形的个数是 O(n2.136) 级别的。
然后就可以用这个结论搞事情了(
容易发现的是鱼身由三个等腰三角形构成。
首先枚举 A,枚举 B,C,计算每对 B,C 左右两边各有多少个 A。
然后枚举 D,枚举 B,C,就可以得到 AD 所在直线和对应的 A 的个数。
随便取一个 A 算极角(代码实现里取的是 →DB+→DC 的终点),然后对极角排序。
然后考虑枚举 E,F,容易发现合法的极角也是一个区间。
二分一下就可以算答案了。
代码:
1 |
|