算法——求圆上点能构成三角形的数目

输入：n——点的个数，a：double的点的角度。

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include <string>
 8 
 9 
10 using namespace std;
11 
12 bool compare(vector<double> b, size_t slow, size_t fast, size_t length)
13 {
14     if (fast < length)
15     {
16         return (b[fast] - b[slow]) < 180;
17     }
18     else
19     {
20         return (360 - b[slow] + b[fast]) < 180;
21     }
22 }
23 
24 long func2(vector<double>& a)
25 {
26     size_t length = a.size();
27     long ret = 0;
28     size_t slow = 0, fast = 1;
29     vector<double> b(a);
30     b.insert(b.end(), a.begin(), a.end());
31     for (slow = 0; slow < length; ++slow)
32     {
33         while (compare(b, slow, fast, length))
34         {
35             ++fast;
36         }
37         fast--;
38         ret += (fast / 2 - slow / 2 - 1)*(fast - slow + 1) + 1;
39         
40     }
41     return ret;
42 }
43 
44 
45 int main()
46 {
47 
48     int n;
49     vector<double> a;
50     scanf("%d", &n);
51     a.resize(n);
52     for (int i = 0; i < n; ++i)
53     {
54         scanf("%lf", &a[i]);
55     }
56 
57     long ret = func2(a);
58     printf("%d\n", ret);
59 
60     return 0;
61 }