## Description
给出圆周上的 $n$ 个点，已知点与点之间的弧长，其值均为正整数，并依照圆周顺序排列。求从中选出 $4$ 个点且能围成矩形的方案数。$(1 \leq n \leq 20)$
## Solution
最容易想到的方法是维护前缀和数组，枚举 $4$ 个点，计算点与点之间的弧长，判断相对的两条弧是否都相等即可（弧长相等，所对的弦长也相等，即矩形的对边相等）。时间复杂度为 $O({\rm C}_n^4)$，由于题目数据范围很小，可以轻松过。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}
template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}
const int MAXN = 20;
int n, sum, ans, a[MAXN + 5], pre[MAXN + 5];
int main() {
read(n);
for (int i = 1; i <= n; ++i) {
read(a[i]);
pre[i] = pre[i - 1] + a[i];
}
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
for (int k = j + 1; k <= n; ++k)
for (int l = k + 1; l <= n; ++l) {
int a = pre[i] + pre[n] - pre[l], b = pre[j] - pre[i],
c = pre[k] - pre[j], d = pre[l] - pre[k];
//a,b,c,d 表示 4 个点把圆分成 4 段弧的长度各是多少，
//注意 a 要拆成两条弧算。
if (a == c && b == d) ++ans;//相对的两条弧都相等
}
write(ans);
putchar('\n');
return 0;
}
```
稍微聪明一点的做法？
首先要知道圆内接矩形的对角线是该圆的直径，因为 $90^\circ$ 圆周角所对的弦是直径。假设有 $cnt$ 条直径，那么任意 $2$ 条不同的直径都能组成一个新的矩形，答案即为 ${\rm C}_{cnt}^2$ 。我们只需要枚举 $2$ 个点，判断这 $2$ 个点之间的距离是不是圆周长的一半，就可以得到直径的数量。时间复杂度为 $O({\rm C}_n^2)$ 。
注意特判圆周长是奇数时无解（所给的弧都是正整数，但半圆是小数，说明不存在直径），但是数据水不特判能过。
$\rm hack$ 数据：
**Input**
```
5
5 1 1 5 1
```
**Output**
```
0
```
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}
template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}
const int MAXN = 20;
int n, cnt, pre[MAXN + 5];
int main() {
read(n);
for (int x, i = 1; i <= n; ++i) {
read(x);
pre[i] = pre[i - 1] + x;
}
if (pre[n] & 1) {//特判圆周长是奇数的情况
puts("0");
return 0;
}
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
if (pre[j] - pre[i] == pre[n] / 2)//判断两点间弧长是否为圆周长的一半
++cnt;
write(cnt * (cnt - 1) / 2);//答案为 C(cnt, 2)
putchar('\n');
return 0;
}
```
由于前缀和数组是单调递增的，我们甚至还可以用二分查找把时间复杂度优化到 $O(n \log n)$ 。
即把枚举过程换成：
```cpp
for (int i = 1; i <= n; ++i)
if (binary_search(pre + i + 1, pre + n + 1, pre[i] + pre[n] / 2))
++cnt;//用 STL 中的 binary_search 检查是否存在合法的 j
```
当然，由于这个单调递增的性质，也可以用尺取法（双指针法），时间复杂度为 $O(n)$ 。
```cpp
for (int l = 1, r = 2; l <= n && r <= n; ) {
if (pre[r] - pre[l] < pre[n] / 2) ++r;
//若两点间的弧长小于圆周长的一半，则移动右端点，使弧长增大
else if (pre[r] - pre[l] > pre[n] / 2) ++l;
//若两点间的弧长大于圆周长的一半，则移动左端点，使弧长减小
else ++l, ++r, ++cnt;
//若两点间的弧长等于圆周长的一半，则更新 cnt，
//同时移动左端点和右端点，寻找新的直径
}
```
## Code
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}
template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}
const int MAXN = 20;
int n, cnt, pre[MAXN + 5];
int main() {
read(n);
for (int x, i = 1; i <= n; ++i) {
read(x);
pre[i] = pre[i - 1] + x;
}
if (pre[n] & 1) {//特判圆周长是奇数的情况
puts("0");
return 0;
}
for (int l = 1, r = 2; l <= n && r <= n; ) {
if (pre[r] - pre[l] < pre[n] / 2) ++r;
//若两点间的弧长小于圆周长的一半，则移动右端点，使弧长增大
else if (pre[r] - pre[l] > pre[n] / 2) ++l;
//若两点间的弧长大于圆周长的一半，则移动左端点，使弧长减小
else ++l, ++r, ++cnt;
//若两点间的弧长等于圆周长的一半，则更新 cnt，
//同时移动左端点和右端点，寻找新的直径
}
write(cnt * (cnt - 1) / 2);
putchar('\n');
return 0;
}
```