凸轮廓线 Convex Contour(数学题)

题目

Convex Contour

问题描述

一些几何图形整齐地在一个网格图上从左往右排成一列。它们占据了连续的一段横行，每个位置恰好一个几何图形。每个图形是以下的三种之一：

1.一个恰好充满单个格子的正方形。

2.一个内切于单个格子的圆。

3.一个底边与格子重合的等边三角形。

已知每个格子的边长都为1，非正式地说，一个排列的凸轮廓是包含所有形状的最短线。在形式上，我们可以将它定义为所有形状联合的凸包的周长。
给定一个形状的排列，找到其轮廓的长度。

分析

需要特别处理三角形的情况，因为三角形的高与另外两个图形不同，以至于在排列后特别考虑一下。

1.当三角形位于正方形或者圆形中间时，由于两边的高度均高于三角形，此时的最短线直接连接两端的图形，横跨三角形即可

2.当有一连串三角形位于一端时，需要考虑此时这一连串三角形后面所接的图形，

如果是正方形，则可以直接连接端点；
如果是圆形，则需要仔细考虑。

（1）当与圆形连接时，很容易误以为最短线就是三角形端点与圆的最高点的连线，但两点连接后会发现，这条线会与圆发生相交；所以这不是真正的最短线
（2）真正的最短线是端点与圆的切线加上切点到圆的最高点的一小段圆弧。
数学问题，切线好求，不会有什么误差；

但圆弧的求法有两种，一种可能是因为浮点数计算过多会产生较大误差，另外一种误差小一些，都写在代码里面了。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>using namespace std;
const int N = 25;
const double eps = 1e-8 ;
double PI = 3.14159265358979;
map<char,double> mp ;
char s[N] ;double F(int p) {
    double ans=p;double s1,s2,l1,l2,j1,j2;l1=sqrt(ans*ans+1.0-sqrt(3)/2.0);s1=sqrt(ans*ans+1.0-sqrt(3)/2.0-0.25);j1=atan((sqrt(3)/2.0-0.5)/ans);j2=acos(0.5/l1);s2=(PI/2.0-j1-j2)/2;// l2=sqrt((1.75-sqrt(3))*(1.75-sqrt(3))+ans*ans); 
// j1=acos((0.25+ans*ans+1.0-sqrt(3)/2.0-((1.75-sqrt(3))*(1.75-sqrt(3))+ans*ans))/l1);
// j2=asin(s1/l1);
// s2=(j1-j2)/2;return s1+s2;
}int main() {
    int n ;cin >> n ;for(int i=1;i<=n;i++)cin>>s[i];double res = 0 ;if( n == 1 ) {
    if( s[1] == 'T' ) res = 3 ;else if( s[1] == 'C' ) res = PI ;else res = 4 ;}else {
    int ans1 = 0, ans2 = 0 ;double flag = 0 ;for(int i = 1 ; i <= n && !flag ; i ++ ) {
    if( s[i] == 'T' ) ans1 ++ ;else flag = 1 ;}flag = 0 ;for(int i = n ; i >= 1 && !flag ; i -- ) {
    if( s[i] == 'T' ) ans2 ++ ;else flag = 1 ;}if( ans1 + ans2 >= n ) res = n + n + 1 ;else if( ans1 && ans2 ) {
    if(ans1 + ans2 == n - 1 ) {
    char c ;for(int i = 1 ; i <= n ; i ++ ) {
    if( s[i] != 'T' ) {
    c = s[i] ;break ;}}if( c == 'C' ) {
    res += n ;res += F(ans1) ;res += F(ans2)  ;res += 2 ;}else {
    res += n + 3 ;res += sqrt( (ans1 - 0.5 ) * (ans1 - 0.5 ) +1.75-sqrt(3) )  ;res += sqrt( (ans2 - 0.5 ) * (ans2 - 0.5 ) +1.75-sqrt(3) ) ;}}else {
    if( s[ans1 + 1] == 'C' ) {
    res += F(ans1)  ;res += 1+ans1+0.5 ;}else if(s[ans1+1]=='S'){
    res += sqrt( (ans1 - 0.5 ) * (ans1 - 0.5 ) + 1.75-sqrt(3) ) ;res += 1+ans1+1 ;}if( s[ n - ans2 ] == 'C' ) {
    res += F(ans2)  ;res += 1+ans2+0.5 ;}else if(s[ n - ans2 ] == 'S'){
    res += sqrt( (ans2 - 0.5 ) * (ans2 - 0.5 ) + 1.75-sqrt(3) ) ;res += 1+ans2+1 ;}res += ( n - ans1 - ans2 - 1 )*2 ;}}else if( ans1 ) {
    // only ans1if( ans1 == n - 1 ) {
    if( s[n] == 'C' ) {
    res += F(ans1)  ;res += PI /2;res += 0.5 ;res += ans1 + 1 ;}else {
    res += sqrt( (ans1 - 0.5 ) * (ans1 - 0.5 ) + 1.75-sqrt(3) ) ;res += 3 + ans1 + 1 ;}}else {
    if( s[ans1+1] == 'C' ) {
    res += F(ans1) ;res += 0.5 + ans1 + 1 ;}else {
    res += sqrt( (ans1 - 0.5 ) * (ans1 - 0.5 ) +1.75-sqrt(3) )  ;res += 1+ ans1 + 1 ;}if( s[n] == 'C' ) {
    res+=(n-ans1-1)*2+PI/2;}else {
    res+=(n-ans1-1)*2+ 2 ;}}}else if( ans2 ) {
    // only ans2ans1 = ans2 ;reverse(s+1,s+1+n) ;if( ans1 == n - 1 ) {
    if( s[n] == 'C' ) {
    res += F(ans1) ;res += PI /2;res += 0.5 ;res += ans1 + 1 ;}else {
    res += sqrt( (ans1 - 0.5 ) * (ans1 - 0.5 ) +1.75-sqrt(3) ) ;res += 3 + ans1 + 1 ;}}else {
    if( s[ans1+1] == 'C' ) {
    res += F(ans1) ;res += 0.5 + ans1 + 1 ;}else {
    res += sqrt( (ans1 - 0.5 ) * (ans1 - 0.5 ) + 1.75-sqrt(3) ) ;res += 1+ ans1 + 1 ;}if( s[n] == 'C' ) {
    res+=(n-ans1-1)*2+PI/2;}else {
    res+=(n-ans1-1)*2+2 ;  }}}else {
    res += ( n - 1 ) * 2 ;if( s[1] == 'C' ) {
    res += PI / 2 ;}else res += 2 ;if( s[n] == 'C' ) {
    res +=  PI / 2 ;}else res += 2 ;}}printf("%.9lf\n",res) ;return 0 ;
}