#P4789. [CERC2016]Convex Contour

    ID: 3906 传统题 1000ms 512MiB 尝试: 44 已通过: 25 难度: 6 上传者: 标签>难度分类提高计算几何凸包构造与建模对称性分析点到圆的切线与圆弧长度CF1900

[CERC2016]Convex Contour

[CERC2016] 凸轮廓线 Convex Contour

题目描述

一行连续的单位正方形格子中,每格恰有一个图形。图形共有三种。

  • S 是与格子完全重合的正方形。
  • C 是内切于格子的圆。
  • T 是底边与格子底边重合、顶点朝上的等边三角形。

样例一的图形排列及其凸轮廓线

包围这些图形的最短闭合轮廓,就是所有图形并集的凸包边界。求这条轮廓的长度。

输入格式

第一行一个整数 nn,表示图形的数量。第二行一个长为 nn 的字符串,从左至右描述各格中的图形。字符均为 S、C 或 T。

输出格式

输出一个实数,表示凸包周长。绝对误差或相对误差小于 10−610^{-6} 的答案会被接受。

数据范围

1≤n≤201\le n\le20。

样例 #1

样例输入 #1

4
TSTC

样例输出 #1

9.088434417

样例 #2

样例输入 #2

3
SCT

样例输出 #2

7.50914177324