竟然没人写题解 蒟蒻的第一篇题解

题目大意

一个圆周上有N个点，问能构成多少个矩形

做法

20%pts n≤50

直接枚举所有$C_n^4$选法，判断是否合法 复杂度：$O(n^4)$

50%pts n≤5000

注意到
圆上四点能构成矩形，当且仅当：

这四点可以分成两对，每对点都是圆的一条直径的两个端点。

所以只需统计能构成的直径数量

• 枚举所有点对$(i,j)$，计算他们的弧长
• 如果弧长等于圆周总长L/2，则$(i,j)$构成一条直径

当L为奇数时任意两点间弧长都不可能是L/2，所以答案为0

• 统计直径数量d，则答案为$C_d^2$

复杂度:$O(n^2)$

100%pts n≤50000

$n^2$很明显过不了 考虑只枚举一个点，判断到这个点弧长L/2的位置是否有点，如果有就++d
注意：
这里的d是能构成直径的点的数量所以要/2 复杂度：$O(n+L)$