数据量最大的30W,所以只能用O(n)的算法。每次只能枚举一个点,然后我们观察到,在圆上,点A,和A点所处直径对应的点B和原上任意的点C,这三个点形成的三角形是一个直角三角形(初中学过的)。A,B可以把圆分为两个半圆,我们如果找到其中一个半圆夹杂的任意两个点D,E,那么A,D,E形成的三角形一定是钝角,因为对应的弧长是大于圆周的一半的。可以在图上画画试试。所以最后的AC代码为:
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 300007;
double angle[maxn];
int n;
const double eps = 1e-10;
int bi_search(double x) {
int low = 1;
int high = n;
while (low <= high) {
int mid = (low + high) / 2;
if (angle[mid] > x) {
high = mid - 1;
}
else if (fabs(angle[mid] - x) < eps) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
return high;
}
long long getAns(int cnt_a) {
double p1 = angle[cnt_a];
double p2 = p1 + 180.0;
long long result = 0;
if (fabs(p2 - 360) <= eps) {
long long cnt_num = n - cnt_a;
result += (cnt_num * (cnt_num - 1) / 2);
cnt_num = cnt_a - 1;
if (fabs(angle[0]) <= eps) {
cnt_num--;
}
result += (cnt_num * (cnt_num - 1) / 2);
}
else if (p2 < 360) {
int loc = bi_search(p2);
long long cnt_num = loc - cnt_a;
result += (cnt_num * (cnt_num - 1) / 2);
cnt_num = n - loc;
if (fabs(angle[loc + 1] - p2) <= eps) {
cnt_num--;
}
cnt_num += cnt_a - 1;
result += (cnt_num * (cnt_num - 1) / 2);
}
else {
p2 -= 360;
int loc = bi_search(p2);
long long cnt_num = n - cnt_a + loc;
result += (cnt_num * (cnt_num - 1) / 2);
cnt_num = cnt_a - loc - 1;
if (fabs(angle[loc + 1] - p2) <= eps) {
cnt_num--;
}
result += (cnt_num * (cnt_num - 1) / 2);
}
return result;
}
int main() {
// freopen("in.txt", "r", stdin);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lf", &angle[i]);
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
long long cnt_ans = getAns(i);
ans += cnt_ans;
}
cout << ans / 2 << endl;
}