| Solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| 8/10 | O | O | O | O | . | Ø | Ø | O | O | . |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A - Jin Yong’s Wukong Ranking List
题目描述
给定一堆排名顺序，求在第几个出现矛盾。
解题思路
爆搜判环即可。
AC代码 - by Mogg
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
using namespace std;
map<string, set<string>>m;
void dfs(const string& now, const string& to)
{
for (const string& i : m[to])
{
dfs(now, i);
}
m[now].insert(to);
}
int main()
{
string a, b;
int n;
while (cin >> n)
{
m.clear();
vector<pair<string, string>> res;
for (int i = 0; i < n; ++i)
{
cin >> a >> b;
if (m[a].count(b))
{
res.emplace_back(a, b);
}
else
{
dfs(b, a);
}
}
if (res.empty()) cout << 0 << "\n";
for (auto i : res)
{
cout << i.first << " " << i.second << "\n";
}
}
}
B - Heshen’s Account Book
题目描述
给定$n$行，相邻两行最后一个字符和第一个字符都是数字则可拼接，求出数字个数并输出每行数字数量。
解题思路
非常神秘的细节题，先拼接、标记再输出答案。
AC代码 - by Mogg
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
using namespace std;
bool isNum(const string&s)
{
if (s.empty()) return false;
if (s.size() == 1)
{
return s[0] >= '0' && s[0] <= '9';
}
if (s.size() > 1)
{
return s[0] > '0' && s[0] <= '9' && *s.rbegin() >= '0' && *s.rbegin() <= '9';
}
return false;
}
int main()
{
int n = 0;
string s;
vector<vector<string>> lines;
vector<string> tmp;
while (getline(cin, s))
{
tmp.push_back(s);
n++;
}
for (int i = n - 1; i > 0; --i)
{
if (isdigit(*tmp[i - 1].rbegin()) && isdigit(*tmp[i].begin()))
{
int j = 0, len = tmp[i].size();
for (; j < len && isdigit(tmp[i][j]); j++);
tmp[i - 1] += tmp[i].substr(0, j);
tmp[i] = tmp[i].substr(j);
}
}
for (int i = 0; i < n; ++i)
{
stringstream ss(tmp[i]);
string t;
vector<string> tt;
while (getline(ss, t, ' '))
{
if (!t.empty())
tt.push_back(t);
}
lines.push_back(tt);
}
vector<int> res(n, 0);
vector<string> rs;
for (int i = 0; i < n; ++i)
{
int len = lines[i].size();
for (int j = 0; j < len; ++j)
{
if (isNum(lines[i][j]))
{
rs.push_back(lines[i][j]);
res[i]++;
}
}
}
for (const string& i : rs)
{
cout << i << " ";
}
cout << "\n";
for (int i : res)
{
cout << i << "\n";
}
}
C - Pythagorean triple
题目描述
求出满足$a^2+b^2=c^2,c\leq n$且$a,b,c> 0$的三元组个数。
解题思路
$a^2+b^2=c^2$，于是$(a^2-b^2)^2+(2ab)^2=c^2$。故$a,b,c$必可表示为$a=x^2-y^2,b=2xy,c=x^2+y^2$的形式。易证，其中$a,b$必为一奇一偶，$c$必为奇数。
设$f(x)$表示$c\leq x$的三元组数，$g(x)$表示本原的$c\leq x$的三元组数（即$gcd(a,b)=1$）。再设$F,G$分别为$f,g$的前缀和。那么有如下关系：
$g(n)=\sum_{x=1}^{n}\sum_{y=1}^{n}[x^2+y^2=n][gcd(x,y)=1][x>y]([x\space is\space odd][y\space is\space even]or[x\space is\space even][y\space is\space odd])$
$=\sum_{x=1}^{n}\sum_{y=1}^{n}[x^2+y^2=n][gcd(x,y)=1][x\space is\space odd][y\space is\space even]$
$f(x)=\sum_{d|x}g(d)$
$F(n)=\sum_{i=1}^{n}f(i)=\sum_{i=1}^{n}\sum_{d|i}g(d)=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac nd \rfloor}g(i)=\sum_{d=1}^{n}G(\lfloor\frac nd\rfloor)$
$G(n)=\sum_{i=1}^{n}g(i)$
$=\sum_{x=1}^{n}\sum_{y=1}^{n}[x^2+y^2\leq n][gcd(x,y)=1][x\space is\space odd][y\space is\space even]$
$=\sum_{x=1,x\space is\space odd}^{n}\sum_{y=1,y\space is\space even}^{n}[x^2+y^2\leq n]\sum_{d|gcd(x,y)}\mu(d)$
$=\frac12\sum_{d=1}^{\sqrt{\frac n2}}(\sum_{x=1}^{n}\sum_{y=1}^{n}-\sum_{x=1,x\space is\space odd}^{n}\sum_{y=1,y\space is\space odd}^{n})[x^2+y^2\leq n][d|x][d|y]$
$=\frac12\sum_{d=1}^{\sqrt{\frac n2}}(\sum_{i=1}^{\lfloor\frac{\sqrt{n}}d\rfloor}\sum_{y=1}^{n}[i^2d^2+y^2\leq n][d|y]-\sum_{i=1,id\space is\space odd}^{\lfloor\frac{\sqrt{n}}d\rfloor}\sum_{y=1}^{n}[i^2d^2+y^2\leq n][d|y])$
$=\frac12\sum_{d=1}^{\sqrt{\frac n2}}(\sum_{i=1}^{\lfloor\frac {\sqrt{n}}d\rfloor}\sum_{j=1}^{\lfloor\frac {\sqrt{n-i^2d^2}}d\rfloor}1-\sum_{i=1,id\space is\space odd}^{\lfloor\frac {\sqrt{n}}d\rfloor}\sum_{j=1,jd\space is\space odd}^{\lfloor\frac {\sqrt{n-i^2d^2}}d\rfloor}1)$
$=\frac12\sum_{d=1}^{\sqrt{\frac n2}}(\sum_{i=1}^{\lfloor\frac {\sqrt{n}}d\rfloor}{\lfloor\frac {\sqrt{n-i^2d^2}}d\rfloor}-[d\space is\space odd]\sum_{i=1,i\space is\space odd}^{\lfloor\frac {\sqrt{n}}d\rfloor}\sum_{j=1,j\space is\space odd}^{\lfloor\frac {\sqrt{n-i^2d^2}}d\rfloor}1)$
至此，可以看出，$G(n)$可以通过对$i$数论分块做到较低的复杂度，求$F$时对$G$数论分块即可。
可以通过预处理出$G(n)$的前部分项进一步减小复杂度。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
typedef long long ll;
using namespace std;
int isnp[N],mu[N],pr[N],tot;
void sieve(){
int i,j;
isnp[0]=isnp[1]=1;
mu[1]=1;
for(i=2;i<N;i++){
if(!isnp[i])pr[tot++]=i,mu[i]=-1;
for(j=0;j<tot;j++){
if(pr[j]*i>=N)break;
isnp[pr[j]*i]=1;
if(i%pr[j])mu[i*pr[j]]=-mu[i];
else{
mu[i*pr[j]]=0;
break;
}
}
}
}
ll G[MAX+10];
void initG(){
ll i,j;
for(i=1;i<=MAX;i+=2){
ll mx=sqrt(MAX-i*i);
for(j=2;j<=mx;j+=2)if(__gcd(i,j)==1)G[i*i+j*j]++;
}
for(i=1;i<=MAX;i++)G[i]+=G[i-1];
}
ll getG(int n){
if(n<=MAX)return G[n];
ll i,res=0,d,mx=sqrt(n/2);
for(d=1;d<=mx;d++){
ll r,temp=0,my=ll(sqrt(n))/d,p;
for(i=1;i<=my;i=r+1){
p=sqrt(n-(i*d)*(i*d))/d;
r=sqrt(n-(p*d)*(p*d))/d;
temp+=p*(r-i+1);
if(d&1)temp-=(p+1)/2*((r-i+1+(i%2))/2);
}
temp*=mu[d];
res+=temp;
}
return res/2;
}
int main(){
int i,r,T,n;
sieve();
initG();
scanf("%d",&T);
while(T--){
ll ret=0;
scanf("%d",&n);
for(i=1;i<=n;i=r+1){
r=n/(n/i);
ret+=getG(n/i)*(r-i+1);
}
printf("%lld\n",ret);
}
return 0;
}
D - Frog and Portal
题目描述
有一只青蛙要从$0$跳到$200$，每次可以向前跳一格或者两格。
你可以加一些传送门，当青蛙跳到其起点时会被立即传送到传送门的终点。
要求青蛙从$0$跳到$200$总方案数为$M(0\leq M<2^{32})$，求传送门安装方案。
解题思路
第一感是斐波那契数列，但其实完全可以依靠$1$的特殊性来做这个题。
如果$M$为奇数，从$1$连向$200$一个传送门，表示第一次跳跃到$1$时有一种到达$200$的方案，问题转化为起点为$2$的$M_2=M-1$的方案设计。
如果$M$为偶数，连接传送门$1\rightarrow3,2\rightarrow3$，问题转化为起点为$3$的$M_2=\frac M2$的方案设计。
当$M=0$时，连接传送门$3\rightarrow1,2\rightarrow1$，表示这个点出不去了。
就没了。神仙构造。
AC代码 - by Mogg
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
typedef long long ll;
using namespace std;
int main()
{
ll m;
while (cin >> m)
{
vector<pair<int, int>> res;
int cur = 0;
while (m > 0)
{
if (m & 1)
{
res.emplace_back(cur + 1, 199);
m -= 1;
cur = cur + 2;
}
else
{
res.emplace_back(cur + 1, cur + 3);
res.emplace_back(cur + 2, cur + 3);
m /= 2;
cur = cur + 3;
}
}
if (m == 0)
{
res.emplace_back(cur + 1, cur + 1);
res.emplace_back(cur + 2, cur + 1);
}
cout << res.size() << "\n";
for (auto i : res)
{
cout << i.first << " " << i.second << "\n";
}
}
}
E - Xor 2
题目描述
解题思路
AC代码
2
F - The Kth Largest Value
题目描述
给一个有向图，定义$(u,v)$是好的当且仅当$u$可以通过某些路径到达$v$。如果$(u,v)$是好的，这一个偶对的权值定义为$u\oplus v$。
$q$次询问，每次求第$k$大的好的偶对的权值。
$n\leq 50000,m\leq 200000,q\leq 10,T\leq 3$
解题思路
首先可以通过缩点将所有$u$能够直接连到的$v$存入一个$bitset$中（$bs[col[i]][j]=1$当且仅当$i$能走到$j$），再通过逆向拓扑排序求出所有$u$能够到达的$v$的集合。
对每次询问，我们想象一棵二叉$trie$，从上到下贪心地选择$0$或者$1$，当当前选择$1$后能够到达的点数总和$\geq k$时可以选择$1$，否则选择$0$。故枚举每个点，求有多少个点满足能够从$i$连过来且值在某区间内。这样通过求$bitset$的前缀和可以求解，但是这样的复杂度是$O(n^2+n\log n)$的，预处理复杂度太大。
考虑分块。将$bitset$分成$block$块，把每块看成一个整体求前缀和，这样预处理复杂度$O(\frac{n^2}{block})$，询问复杂度$O(q\times 2nblock\times \log n)$，空间复杂度$O(\frac{n^2}{block})$，实测$block$取$40$的时候可以非常极限地卡过。
（集齐五种错误即可召唤AC .jpg）
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
typedef long long ll;
using namespace std;
int n;
bitset<block>bs[N][M/block+3];
int sb[N][M/block+3];
struct Edge{
int e,n;
}e[N<<3];
int hd[N],cnt;
void add(int a,int b){
e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;
}
int vmin[N];
int sta[N],top,vis[N];
int col[N],num;
int dfn[N],low[N],tot;
void tarjan(int p){
int i,q;
low[p]=dfn[p]=++tot;
sta[++top]=p;vis[p]=1;
for(i=hd[p];i;i=e[i].n){
q=e[i].e;
if(!dfn[q])tarjan(q),low[p]=min(low[p],low[q]);
else if(vis[q])low[p]=min(low[q],low[p]);
}
if(dfn[p]==low[p]){
num++;
while(sta[top+1]!=p){
q=sta[top];
bs[num][q/block][q%block]=1;
col[q]=num;
vis[q]=0;
top--;
}
}
}
void initbs(){
int i,j;
for(i=1;i<=num;i++)for(j=0;j<=M/block;j++){
sb[i][j]=bs[i][j].count();
if(j)sb[i][j]+=sb[i][j-1];
}
}
int a[N<<2],b[N<<2],ind[N];
queue<int>Q;
int getnum(int p,int l,int r){//[l,r)
int i,s;
if(r>=M)r=M-1;
if(r/block-l/block<=1){
s=0;
for(i=l;i<r;i++)s+=bs[p][i/block][i%block];
return s;
}
s=sb[p][r/block-1]-sb[p][l/block];
for(i=l/block*block+block-1;i>=l;i--)s+=bs[p][i/block][i%block];
for(i=r/block*block;i<r;i++)s+=bs[p][i/block][i%block];
return s;
}
int check(int p,int &k){//can choose 1
int i,s=0,tmp;
for(i=1;i<=n;i++){
tmp=vmin[i];
if(!(i&(1<<p)))tmp+=1<<p;
s+=getnum(col[i],tmp,tmp+(1<<p));
}
if(s>=k)return 1;
k-=s;return 0;
}
void choose(int p,int x){
int i;
for(i=1;i<=n;i++)if(x^(i>>p&1))vmin[i]+=(1<<p);
}
int main(){
int i,j,T,k,q,m;
// double TIM=clock();
// freopen("data.in","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&q);
for(i=0;i<=n;i++)for(j=0;j<=n/block;j++)sb[i][j]=0,bs[i][j].reset();
memset(hd,0,sizeof(hd));cnt=0;
memset(col,0,sizeof(int)*(n+1));num=0;
memset(dfn,0,sizeof(int)*(n+1));
memset(low,0,sizeof(int)*(n+1));tot=0;
memset(ind,0,sizeof(int)*(n+1));
for(i=0;i<m;i++)scanf("%d%d",&a[i],&b[i]),add(a[i],b[i]);
for(i=1;i<=n;i++)if(!dfn[i])tarjan(i);
memset(hd,0,sizeof(hd));cnt=0;
for(i=0;i<m;i++)if(col[a[i]]!=col[b[i]])add(col[b[i]],col[a[i]]),ind[col[a[i]]]++;
for(i=1;i<=num;i++)if(!ind[i])Q.push(i);
while(!Q.empty()){
int now=Q.front();Q.pop();
for(i=hd[now];i;i=e[i].n){
int q=e[i].e;
for(j=0;j<=n/block;j++)bs[q][j]|=bs[now][j];
if(!--ind[q])Q.push(q);
}
}
/*vector<int>V;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(bs[col[i]][j/block][j%block])
V.push_back(i^j);
}
}
sort(V.begin(),V.end());*/
// for(auto j:V)printf("%d ",j);puts("");
initbs();
// printf("%f\n",(clock()-TIM)/CLOCKS_PER_SEC);
while(q--){
scanf("%d",&k);
//int X=k,tmp=V[V.size()-k];
int res=0;
for(i=16;i>=0;i--){
if(check(i,k))choose(i,1),res=res<<1|1;
else choose(i,0),res<<=1;
}
//if(res!=tmp)printf("%d %d %d\n",res,tmp,X);
//assert(res==tmp);
printf("%d\n",res);
memset(vmin,0,sizeof(int)*(n+1));
}
}
// printf("%f",(clock()-TIM)/CLOCKS_PER_SEC);
return 0;
}
G - Solving Equations is Easy
题目描述
给一个$n$次方程，其中所有根（包括复根）为$x_i(1\leq i\leq n)$。求满足所有根为$x_i^m$的$n$次方程。
解题思路
牛顿恒等式：设方程$a_n+a_{n-1}x+a_{n-2}x^2+…+a_0x^n=0$的根为$x_1,x_2,…,x_n$，$S_k=\sum_{i=1}^{n}x_i^k$，则有$\sum_{i=1}^{k}S_ia_{k-i}+ka_k=0(\forall k\in N)$。
列一下前几项简单体会一下：
$S_1a_0+a_1=0$
$S_1a_1+S_2a_0+2a_2=0$
$S_1a_2+S_2a_1+S_3a_0+3a_3=0$
我们发现，可以通过$a$序列递推出所有的$S$，反之亦可。
于是正向推出$S$在$im(1\leq i\leq n)$上的取值，再逆推系数即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
typedef long long ll;
using namespace std;
ll b[N],s[N],res[N];
int main(){
int i,j,n,m;
while(~scanf("%d%d",&n,&m)&&(n|m)){
memset(b,0,sizeof(b));
memset(s,0,sizeof(s));
memset(res,0,sizeof(res));
for(i=n;i;i--)scanf("%lld",&b[i]);
res[0]=b[0]=1;
for(i=1;i<=m*n;i++){
for(j=1;j<i;j++)s[i]-=s[j]*b[i-j];
s[i]-=i*b[i];
s[i]/=b[0];
}
for(i=1;i<=n;i++){
for(j=1;j<=i;j++)res[i]-=s[j*m]*res[i-j];
res[i]/=i;
}
for(i=0;i<n;i++)printf("%lld ",res[n-i]);
puts("");
}
return 0;
}
H - Approximate Matching
题目描述
定义两个串$S,T$为匹配的，当且仅当$S$存在一个子串$s$，满足$s$和$T$最多相差一个字符。
给定长度为$n$的串$T$，以及$S$的长度$m$，求有多少个$S$满足要求。
解题思路
设$f[i][j]$表示$S$从第$i$位开始第一次匹配到$T$，即$S[i…i+n-1]$和$T[1…m]$最多相差一个字符，这个相差的字符在$T_{j}$处，这时的方案数。
于是可以愉快地推式子：
$f[i][j]=2^{m-(i+n-1)}(2^{i-1}-\sum_{k+n-1<i}\sum_{l}f[k][l]\times 2^{i-(k+n)}-\sum_{k+n-1\geq i,k<i}\sum_{l}w_{ijkl}f[k][l])$
解释一下：在匹配区有且仅有一种方法，匹配前后均可任选，再减去前面出现过匹配到$T$的种数即为所求。第一个减去的是上次匹配$[k…k+n-1]$和本次匹配不相交的情况，这两次匹配之间可以任意选择；第二个减去的是两次匹配相交的情况，用$w_{ijkl}$判断需不需要删除，当两个匹配部分的交相等时，需要删除$f[k][l]$的影响。
故预处理出$w_{ijkl}$（不妨固定一个串移动另一个串，枚举$j,l$再线性求即可$O(n^4)$预处理出），再进行$dp$，所有$f[i][j]$的和即为答案。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
typedef long long ll;
using namespace std;
char s[45];
ll f[45][45];
int w[45][45][45],n,m;
int W(int a,int b,int c,int d){
if(a>c)return w[a-c+1][b][d];
return w[c-a+1][d][b];
}
int main(){
int i,j,k,l,T;
scanf("%d",&T);
while(T--){
scanf("%d%d%s",&n,&m,s+1);
memset(w,0,sizeof(w));
for(i=1;i<=n;i++){
for(j=1;j<=n+1;j++){
for(k=1;k<=n+1;k++){
w[i][j][k]=1;
for(l=i;l<=n;l++){
int c1,c2;
if(l-i+1==j)c1=(s[l-i+1]-'0')^1;
else c1=s[l-i+1]-'0';
if(l==k)c2=(s[l]-'0')^1;
else c2=s[l]-'0';
if(c1!=c2){w[i][j][k]=0;break;}
}
}
}
}
memset(f,0,sizeof(f));
ll res=0;
for(i=1;i+n-1<=m;i++){
for(j=1;j<=n+1;j++){
f[i][j]=1LL<<(i-1);
for(k=1;k+n-1<i;k++)
for(l=1;l<=n+1;l++)
f[i][j]-=f[k][l]*(1LL<<(i-n-k));
for(;k<i;k++)
for(l=1;l<=n+1;l++)
f[i][j]-=f[k][l]*W(i,j,k,l);
res+=f[i][j]*(1LL<<(m-(i+n)+1));
}
}
printf("%lld\n",res);
}
return 0;
}
I - Palindromes
题目描述
问第$k$个回文数是多少，$k$的位数在$100000$级别。
解题思路
找规律，推式子+高精度。
AC代码 - by qxforever
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using namespace std;
const int maxn = 1e5+23;
int b[maxn];
char s[maxn];
int len;
void sub(int h)
{
h/=2;
b[h+1]-=2;
for(int i=h;i<=len;i++) if(b[i]<0) b[i]+=10,b[i+1]--;
while(b[len]==0&&len>0) len--;
}
void pp(int &h)
{
int t=(h+1-1)/2+1;
if(len>t||(len==t&&b[t]==9)){
b[t]-=9;
for(int i=t;i<=len;i++){
if(b[t]<0) b[t]+=10,b[t+1]--;
}
while(b[len]==0&&len>0) len--;
h++;
}
}
int ans[maxn];
int main()
{
int T;cin >> T;
while(T--){
scanf("%s",s+1);
len=strlen(s+1);
for(int i=1;i<=len;i++) b[i]=s[i]-'0';
reverse(b+1,b+len+1);
int h;
if(b[len]>=2) h=(len-1)*2;
else h=(len-2)*2;
sub(h);
pp(h);
h++;
memset(ans,0,sizeof(ans));
int t=(h+1)/2;
for(int i=t;i;i--) ans[i]=ans[h+1-i]=b[t+1-i];
ans[1]++;if(h!=1)ans[h]++;
for(int i=1;i<=h;i++) printf("%d",ans[i]);
if(h<=0) printf("0");
puts("");
}
}
J - Rikka with Triangles
题目描述
给$n$个点（$3\leq n\leq 2000$），求所有锐角三角形面积之和。
解题思路
对每个点极角排序，枚举每一条边，二分或者双指针找出两端超出直角区的位置，利用前缀和可求出这部分包含的面积之和。复杂度$O(Tn^2\log n)$。
AC代码 - 待补
2