Convex Contour

Time limit1sMemory limit512 MB

Summary

Given a row of squares, inscribed circles, and equilateral triangles in a unit grid, compute the length of the convex hull boundary of their union.

Level: Medium7 of 10
Topics: Geometry, Math, Implementation, Brute force
Solved: No attempts yet

Problem

Several geometric shapes are lined up inside a rectangular grid. They fill consecutive cells of one row, one shape per cell. Every cell of the grid is a square of side 1. Each shape is one of three kinds:

a square that exactly fills its cell,
a circle inscribed in its cell,
an equilateral triangle whose base is the bottom side of its cell.

The figure shows the arrangement TSTC and its convex contour.

The convex contour of an arrangement is the shortest closed line that encloses every shape. Formally it is the perimeter of the convex hull of the union of all the shapes.

Given an arrangement, compute the length of its convex contour.

Input

The first line contains an integer $n$ ( $1 \le n \le 20$ ), the number of shapes.

The second line contains a string of $n$ characters that describes the shapes from left to right. Each character is S for a square, C for a circle, or T for a triangle.

Output

Print the length of the convex contour rounded to exactly six digits after the decimal point.

Examples2

Example 1
Input
```
4
TSTC
```
Expected output
```
9.088434
```
Example 2
Input
```
3
SCT
```
Expected output
```
7.509142
```