题目链接：Convex Contour
题意：
在格子的一行中给出若干个正方形(S)，等边三角形(T)，圆形(C)，画线将整个图形包围住，求线的最短长度。
思路：
需要分类讨论。
当图形的两端是圆形或正方形的时候，画出最短的线一定全是横的和竖的，即轮廓是一个矩形。
当全是三角形时，画出最短的线只有两端的三角形是斜的，其他的全是横的和竖的，即轮廓是一个梯形。
当两端有三角形而过渡到矩形或圆形时，需要单独计算。
当三角形过渡到圆形时，如图，以圆心为原点，建立平面直角坐标系，AF⊥DF，点A，B，D坐标均知道，圆的半径也知道，
为1/2，可以求出点F坐标，然后求出BF，DF长度，由于△ABF三边长度均知道，根据余弦定理求出∠BAF，这样弧BF的长
也可以求出了(|弧BF| / π = ∠BAF / (2 * π))。
代码：
# include <iostream> # include <algorithm> # include <cstdio> # include <cstring> # include <cmath> using namespace std; typedef long long ll; const int maxn = 20 + 5; const double pi = acos(-1.0); char s[maxn]; int n; double sqr(double x) { return x * x; } struct Point { double x, y; Point() { } Point(double x, double y) : x(x), y(y) { } double operator - (const Point& P) const { return sqrt(sqr(P.x - x) + sqr(P.y - y)); } }; struct Circle { Point P; double r; Circle() { } Circle(Point P, double r) : P(P), r(r) { } }; double f_S(int n) { return sqrt(sqr(n - 0.5) + sqr((2 - sqrt(3)) / 2)); } double f_C(int n) { Point O(0.0, 0.0); Circle C(O, 0.5); Point P(n, (sqrt(3) - 1) / 2); double a = 4 * sqr(n) / sqr(sqrt(3) - 1) + 1; double b = -8 * n * sqr(C.r) / sqr(sqrt(3) - 1); double c = sqr(2 * sqr(C.r)) / sqr(sqrt(3) - 1) - sqr(C.r); double delta = sqr(b) - 4 * a * c; double x0 = (-b - sqrt(delta)) / (2 * a); double y0 = sqrt(sqr(C.r) - sqr(x0)); Point Q(x0, y0), Q2(0, 0.5); double l = P - Q; double cosalpha = (sqr(C.r) * 2 - sqr(Q - Q2)) / (2 * sqr(C.r)); double alpha = acos(cosalpha); double l2 = alpha / 2; return l + l2; return 0; } int main(void) { while (~scanf("%d", &n)) { scanf("%s", s); int len = strlen(s); int cnt1 = 0, cnt2 = 0; for (int i = 0; i < len; ++i) { if (s[i] == 'T') ++cnt1; else break; } for (int i = len - 1; i >= 0; --i) { if (s[i] == 'T') ++cnt2; else break; } double ans = 0; if (cnt1 == n) { ans = n + n - 1 + 2; } else if (cnt1 && cnt2) { int l = cnt1 - 1, r = n - cnt2; ans = 2 + n + (r - 1) - (l + 1); if (s[l + 1] == 'S') ans += 0.5; if (s[r - 1] == 'S') ans += 0.5; if (s[l + 1] == 'S') ans += f_S(cnt1); else if (s[l + 1] == 'C') ans += f_C(cnt1); if (s[r - 1] == 'S') ans += f_S(cnt2); else if (s[r - 1] == 'C') ans += f_C(cnt2); } else if (cnt1) { int l = cnt1 - 1, r = n - 1; ans = n + 0.5; ans += n - cnt1 - 1; if (s[r] == 'S') ans += 2; else if (s[r] == 'C') ans += pi / 2; if (s[l + 1] == 'S') ans += 0.5; if (s[l + 1] == 'S') ans += f_S(cnt1); else if (s[l + 1] == 'C') ans += f_C(cnt1); } else if (cnt2) { int l = 0, r = n - cnt2; ans = n + 0.5; ans += n - cnt2 - 1; if (s[l] == 'S') ans += 2; else if (s[l] == 'C') ans += pi / 2; if (s[r - 1] == 'S') ans += 0.5; if (s[r - 1] == 'S') ans += f_S(cnt2); else if (s[r - 1] == 'C') ans += f_C(cnt2); } else { ans = (n - 1) * 2; int l = 0, r = n - 1; if (s[l] == 'S') ans += 2; else if (s[l] == 'C') ans += pi / 2; if (s[r] == 'S') ans += 2; else if (s[r] == 'C') ans += pi / 2; } printf("%.7f\n", ans); } return 0; }
