ACM-ICPC Asia Training League 暑假第一阶段第五场 BCDI

B 求两个点到圆的切点的距离加上两个切点的弧长

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 1e5+10;
 5 double x,y,gx,gy,xa,xb,xc,ya,yb,yc;
 6 double ans1[4], ans2[4];
 7 double dis(double x1, double y1, double x2, double y2) {
 8     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
 9 }
10 
11 int main() {
12     double x, y, gx, gy, x1, y1, r1, x2, y2, r2;
13     cin >> x >> y >> gx >> gy >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
14     double xx1 = dis(x,y,x2,y2);
15     double xx2 = dis(gx,gy,x2,y2);
16     double ans1 = sqrt(xx1*xx1-r2*r2);
17     double ans2 = sqrt(xx2*xx2-r2*r2);
18     double xx3 = dis(x,y,gx,gy);
19     double a1 = acos(r2/xx1);
20     double a2 = acos(r2/xx2);
21     double a3 = acos((xx1*xx1+xx2*xx2-xx3*xx3)/(2*xx1*xx2));
22     double ans3 = (a3-a2-a1)*r2;
23     printf("%.10f
",ans1+ans2+ans3);
24     return 0;
25 }

C 滑雪问题，m条路径，从高处往地处滑，求能滑的最长路径是多少，从低往高处求，dfs可以过。

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 1e3+10;
 5 typedef pair<int,int> P;
 6 vector<P> vs[N];
 7 int d[N];
 8 void dfs(int v) {
 9     for(auto p : vs[v]) {
10         int u = p.first, w = p.second;
11         if(d[u] < d[v] + w) {
12             d[u] = d[v] + w;
13             dfs(u);
14         }
15     }
16 }
17 int main() {
18     int n, m;
19     cin >> n >> m;
20     for(int i = 0; i < m; i ++) {
21         int u, v, w;
22         cin >> u >> v >> w;
23         vs[v].push_back(P(u,w));
24     }
25     for(int i = 1; i <= n; i ++) {
26         dfs(i);
27     }
28     int MAX = 0;
29     for(int i = 1; i <= n; i ++) MAX = max(MAX, d[i]);
30     printf("%d
",MAX);
31     return 0;
32 }

D n个数，求有多少中由n+1个数组成的

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 using namespace std;
 4 int n, x, MIN1 = INF, MIN2 = -INF;
 5 int main() {
 6     cin >> n;
 7     int tmp = 0;
 8     for(int i = 1; i <= n; i ++) {
 9         cin >> x;
10         tmp = x - tmp;
11         if(i&1) MIN1 = min(MIN1, tmp);
12         else MIN2 = max(MIN2,-tmp);
13     }
14     if(MIN2>MIN1) printf("0
");
15     else if(MIN2 < 0 && MIN1 < 0) printf("0
");
16     else if(MIN2 < 0 && MIN1 >= 0) printf("%d
",MIN1+1);
17     else printf("%d
",MIN1-MIN2+1);
18     return 0;
19 }

I 前面的等级大于后面的，只要前面的赢了后面的就一点赢，全部平均也算英雄赢。

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 1e5+10;
 5 int n;
 6 int a[N], b[N];
 7 int main() {
 8     int x;
 9     cin >> n;
10     for(int i = 0; i < n; i ++) cin >> a[i];
11     for(int i = 0; i < n; i ++) cin >> b[i];
12     int id = b[0] - a[0];
13     if(id < 0) return 0*printf("0
");
14     for(int i = 1; i < n; i ++) {
15         if(b[i] - a[i] > id) {
16             return 0*printf("%d
",id+1);
17         } else if(b[i] - a[i] < id) {
18             return 0*printf("%d
",id);
19         }
20     }
21     printf("%d
",id);
22     return 0;
23 }