BZOJ 1800: [Ahoi2009]fly 飞行棋 （尺取+数学）
1800: [Ahoi2009]fly 飞行棋
Time Limit: 10 Sec Memory Limit: 64 MB Submit: 1530 Solved: 1220 [Submit][Status][Discuss]
Description
给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。 请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形。
Input
第一行为正整数N，表示点的个数，接下来N行分别为这N个点所分割的各个圆弧长度
Output
所构成不重复矩形的个数
Sample Input
8 1 2 2 3 1 1 3 3
Sample Output
3
HINT
N<= 20
思路：一开始的想法是枚举四条边，如果a==c&&b==d，就认为是找到了一个矩形。
重点在于判重，非常不好判断。一开始想要根绝四条边的长度hash一下，但是设想一个所有弧长都相等，且弧长较多的情况。
此时所有矩形的边长长度都相同，但是显然是不同的矩形，因此这种判断方法是错误的。
比较棒的思路是：矩形的对角线一定是外接圆的直径。
因此只需要找有多少条执行，假设为c，那么答案就是c*(c-1)/2（因为任意两条对角线就可以构成一个矩形）
这种做法的好处很明显，不需要判重。
至于如何找直径，直径是把圆周等分的弦，所以尺取找一下就好了。
复杂度O(n)
1/* ***********************************************
2Author :111qqz
3Created Time :2017年01月26日 星期四 18时43分21秒
4File Name :code/bzoj/r1800.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=25;
34int n,m;
35int a[N];
36int sum=0;
37LL ans=0;
38void ruler()
39{
40 int head;
41 int tail;
42 int cur = 0 ;
43 head = tail = 1;
44 while (head<n)
45 {
46 cur+=a[head];
47 while (cur>sum) cur-=a[tail++];
48 if (cur==sum)
49 {
50 ans++;
51 }
52 head++;
53 }
54
55}
56int main()
57{
58 #ifndef ONLINE_JUDGE
59// freopen("code/in.txt","r",stdin);
60 #endif
61
62 scanf("%d",&n);
63 for ( int i = 1 ;i <= n ; i++)
64 {
65 scanf("%d",&a[i]);
66 sum = sum + a[i];
67 }
68 //cout<<"sum:"<<sum<<endl;
69 if (sum%2==1)
70 {
71 puts("0");
72 return 0;
73 }
74 sum/=2;
75 ruler();
76 //cout<<"sum:"<<sum<<" ans:"<<ans<<endl;
77 ans=ans*(ans-1)/2;
78 printf("%lld\n",ans);
79 #ifndef ONLINE_JUDGE
80 fclose(stdin);
81 #endif
82 return 0;
83}