[BZOJ1800] [Ahoi2009] fly 飞行棋

Description

　　给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形。

Input

　　第一行为正整数N，表示点的个数，接下来N行分别为这N个点所分割的各个圆弧长度

Output

　　所构成不重复矩形的个数

Sample Input

8
1
2
2
3
1
1
3
3

Sample Output

HINT

　　N<= 20

Source

Solution

　　暴力枚举四个点组成的四边形，检查对边是否相等

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int a[25][25];
 4 int main()
 5 {
 6     int n, ans = 0;
 7     cin >> n;
 8     for(int i = 1; i <= n; i++)
 9         cin >> a[i][i + 1];
10     a[n][1] = a[n][n + 1];
11     for(int i = 1; i <= n; i++)
12         for(int j = i + 2; j != i; j = j % n + 1)
13         {
14             if(j > n) j -= n;
15             if(j == 1) a[i][j] = a[i][n] + a[n][1];
16             else a[i][j] = a[i][j - 1] + a[j - 1][j];
17         }
18     for(int i = 1; i <= n; i++)
19         for(int j = i + 1; j <= n; j++)
20             for(int k = j + 1; k <= n; k++)
21                 for(int l = k + 1; l <= n; l++)
22                     if(a[i][j] == a[k][l] && a[j][k] == a[l][i])
23                         ans++;
24     cout << ans << endl;
25     return 0;
26 }

View Code

　　等等！这题意和题目名称有关系吗？？？