题解 P3680 【[CERC2016]凸轮廓线 Convex Contour】

这是我AC的第一道紫题，正好看到没有人发题解，就自己来一篇 ```cpp #include<bits/stdc++.h>//万能头文件。不用担心，时间不会超~ using namespace std; char ch[20];//(1<=n<=20),只用开20位哦~ double ans;//一定要记得开double，不然凉了不要怪我~ const double pi=3.1415926535;//背过圆周率很重要~ int main() { int n; double p=0;//p记录'S'或'C'之前三角形的数量，出现新的'S'或'C'的时候要记得清零 int flag=0;//很少见的int类型的flag，没办法，要存三个(0代表'T',1代表'S',2代表'C') scanf("%d",&n);//输入这个没用的n，你会发现完全可以用一个strlen函数求出来n~ cin>>ch;//输入这个图形串~ // 下面就要开始计算了，我先给大家来一个详细解释： // 1.这道题里面最坑的，肯定是'T'，因为这是一个等边三角形，它的高度是sqrt(3)，这就不太好办了 // 2.'S'和'C'就要舒服很多了，因为他们的高度都是1，只不过是'C'需要计算一个圆周率而'S'直接用边长解就行了 // 3.我们会发现当一个'T'的两边都有'S'或'C'的时候并不用去管他，只需要ans加这中间三角形的数量数就行了 // 4.最难的点就在于'T'要是出现在两边，这样会很麻烦，除非整个图形都是有'T'组成的，我前面已经说过，'T'要比'S'和'C'低，这时候就需要极强的数学运算能力了 // 5.我的解题思路是把轮廓线分为好几部分： // (1)第一部分是底部的轮廓线，因为有'C'的存在所以我为了方便就先不计入'T'和'S'在两端的时候两头的0.5 // (2)第二部分是两端的轮廓线，如果是'C'的话我们就只需要加一个半圆的弧长，就是pi/2，如果是'T'或'S'的话就要加上两端还没有加上的0.5和'T'的斜边1或是'S'的纵边加上上边的2 // (3)第三部分是上面的部分，要是只有'S'和'C'就好办多了，但是横空毛坯出来了一个可恶的'T'，的确让我废了不上功夫，要是到'T'出现在两边的话如果和'S'相邻还好办一些，只需要让ans加上一个从最头起的三角形的顶点到正方形顶点的连线的长度，而如果'T'和'C'相邻的话可就麻烦了，我们需要让ans加上一个过最头起的三角形顶点做圆的切线的长度和从切点到圆的顶端的弧长 ans+=n-1;//计算轮廓线的第一部分，因为两端分别加除去了0.5，所以ans要加的是n-1~ // 计算轮廓线的第二部分，分别找出字符串的第0位和第n-1位(最左端和最右段) if(ch[0]=='C')//最左端是圆的情况 { flag=2;//用flag标记 ans+=pi/2;//ans加上半圆的弧长 } if(ch[n-1]=='C')//最右段是圆的情况 ans+=pi/2;//ans加上半圆的弧长 if(ch[0]=='T')//最左端是三角形的情况 { p+=1.0;//记录三角形数量 flag=0;//用flag标记 ans+=1.5;//ans加上三角形底边剩余0.5和斜边的1 } if(ch[n-1]=='T')//最右段是三角形的情况 ans+=1.5;//ans加上三角形底边剩余0.5和斜边的1 if(ch[0]=='S')//最左边是正方形的情况 { flag=1;//用flag标记 ans+=2.5;//这里的2.5有些特殊，有底边剩余的0.5和纵边的1加起来的1.5，但哟普与我后面的程序需要在这里加上正方形的上边 } if(ch[n-1]=='S')//最右边是正方形的情况 ans+=1.5;//ans加上正方形底边剩余的0.5和纵边的1 for(int i=1;i<n;i++)//计算轮廓线的第三部分(好多人都是扫了好几遍才扫过，因为数据只有20，所以并不会太受影响，但是数据大了会凉掉的，这里我的循环只用扫一遍，可以承受更强的数据) { if(ch[i]=='T')p+=1.0;//记录三角形数量 if(ch[i]=='S')//读到正方形 { if(flag==1)//前一个高度为1的图形是正方形 { ans+=p+1.0;//ans加上的是中间间隔的三角形数量和此正方形上边的1 p=0;//三角形数量清零 continue;//下面的不用跑了，优化时间复杂度 } if(flag==2)//前一个高度1的图形是圆形 { ans+=p+1.5;//ans加上的是中间间隔的三角形数量，圆形右半部分剩余的0.5和正方形上边的1 p=0; flag=1;//转换flag标记为正方形 continue; } if(flag==0)//前面没有正方形或者是圆形的出现 { ans+=sqrt((p-0.5)*(p-0.5)+(7.0/4.0-sqrt(3)))+1.0;//利用勾股定理可以得出，斜线段的两条直角边分别是最左边三角形的顶点到正方形的距离和此垂线到正方形左上角的1-sqrt(3)/2 p=0; flag=1; continue; } } if(ch[i]=='C')//读到的是圆形 { if(flag==1)//前一位高度为1的图形是正方形 { ans+=p+0.5;//ans加上的是中间间隔三角形的数量和圆形左半部分的0.5 p=0; flag=2; continue; } if(flag==2)//前一位高度为1的图形是圆形 { ans+=p+1.0;//ans加上的是中间间隔的三角形数量，前一个圆形右半部分的0.5和这个圆形右半部分的0.5 p=0; continue; } if(flag==0)//前面没有正方形或者是圆形的出现 { //以下为本题的难点，需要极强的数学运算能力 //这一部分由切线长len1和弧长len2组成 double x=1.0*(p),y=(sqrt(3)/2.0-0.5); double z=sqrt(x*x+1.0-sqrt(3)/2.0); double len1=sqrt(x*x+1.0-sqrt(3)/2.0-0.25);//利用勾股定理求出len1 double o=pi/2.0-atan(y/x)-acos(0.5/z); double len2=0.5*o;//高中的解三角形知识 p=0; ans+=len1+len2;//ans加上这一部分 flag=2; continue; } } } if(p!=0)//有可能结尾最后几个是三角形，这时候剩下的轮廓线还没有加上 { if(flag==1) ans+=sqrt((p-0.5)*(p-0.5)+(7.0/4.0-sqrt(3))); if(flag==2) { double x=1.0*(p),y=(sqrt(3)/2.0-0.5); double z=sqrt(x*x+1.0-sqrt(3)/2.0); double len1=sqrt(x*x+1.0-sqrt(3)/2.0-0.25); double o=pi/2.0-atan(y/x)-acos(0.5/z); double len2=0.5*o; ans+=len1+len2; } if(flag==0)//有可能整个字符串都由三角形组成 ans+=p-1.0;//ans加上中间间隔的p-2个三角形和左右两端两个三角形剩余的0.5，化简以后是p-1 } cout<<fixed<<setprecision(9)<<ans;//此题为special judge，要求精度在10^-6内，为保险起见保留9位小数输出 return 0; } ``` 拿走不谢