UVALive 7749 Convex Contour——模拟

首先求出【三角形，正方形】，【三角形，圆形】的公式，注意【三角形，圆形】要考虑相切，即求一段直线+一段弧长

然后模拟

1.写一个函数，用于计算两个图形间的长度

2.特判N = 1；

3.当N！=1时， 求出【2~N -1】区间内有多少个非三角形

4.没有非三角形：直接计算【1，N】的长度

5.一个非三角形：设这个位置为pos，直接通过第一步写的函数计算【1，pos】和【pos，N】的长度，可能要判断是否对中间的图形计算了多次，即是否需要去重（我的函数需要去重）

6.两个或两个以上的非三角形：求出第一个非三角形和最后一个非三角形，位置设为pos1 pos2，计算【1，pos1】【pos1，pos2】【pos2，N】的长度，同样注意判重

7.计算1和N两边的长度即可

最后注意精度，输出%.6lf

#include #include #include #include #include using namespace std;const double PI = 3.1415926535897;const double sqrt3 = sqrt(3);char str[100];int N;double cal(int i, int j) { double len = 0.0; if (str[i] == 'T' && str[j] == 'T') len = 2.0 * (j - i) + 1; else if (str[i] == 'S' && str[j] == 'S') len = 2.0 * (j - i + 1); else if (str[i] == 'C' && str[j] == 'C') len = 2.0 * (j - i); else if ((str[i] == 'T' && str[j] == 'S') || (str[i] == 'S' && str[j] == 'T')) { len = sqrt((j - i - 0.5) * (j - i - 0.5) + (7.0 / 4.0 - sqrt3)) + 1 + j - i + 1; } else if ((str[i] == 'T' && str[j] == 'C') || (str[i] == 'C' && str[j] == 'T')) { double x = 1.0 * (j - i), y = (sqrt3 / 2.0 - 0.5); double z = sqrt(x * x + 1.0 - sqrt3 / 2.0); double len1 = sqrt(x * x + 1.0 - sqrt3 / 2.0 - 0.25); double o = PI / 2.0 - atan(y / x) - acos(0.5 / z); double len2 = 0.5 * o; len = len1 + len2 + j - i + 0.5; } else if ((str[i] == 'S' && str[j] == 'C') || (str[i] == 'C' && str[j] == 'S')) { len = 2.0 * (j - i + 0.5); } return len;}int main() { while (~scanf("%d", &N)) { scanf("%s", str + 1); double ans = 0.0; if (N == 1) { if (str[1] == 'T') ans = 3.0; else if (str[1] == 'S') ans = 4.0; else if (str[1] == 'C') ans = PI; } else { int cnt = 0; for (int i = 2; i <= N - 1; i++) if (str[i] != 'T') cnt++; if (cnt == 0) { ans = cal(1, N); } else if (cnt == 1) { int pos; for (int i = 2; i <= N - 1; i++) if (str[i] != 'T') { pos = i; break; } ans = cal(1, pos) + cal(pos, N); if (str[pos] == 'S') ans -= 2.0; else if (str[pos] == 'T') ans -= 1.0; } else { int pos1, pos2; for (int i = 2; i <= N - 1; i++) if (str[i] != 'T') { pos1 = i; break; } for (int i = N - 1; i >= 2; i--) if (str[i] != 'T') { pos2 = i; break; } double len1 = cal(1, pos1); if (str[pos1] == 'S') len1 -= 2.0; else if (str[pos1] == 'T') len1 -= 1.0; double len2 = cal(pos2, N); if (str[pos2] == 'S') len2 -= 2.0; else if (str[pos2] == 'T') len2 -= 1.0; ans = len1 + len2 + cal(pos1, pos2); } if (str[1] == 'C') ans += PI * 0.5; else ans += 1.0; if (str[N] == 'C') ans += PI * 0.5; else ans += 1.0; } printf("%.6lf\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。