[CERC2016]凸轮廓线ConvexContour

洛谷题目链接

学习OI以来做的第一道几何题，写篇文章纪念一下。

题目描述

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

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

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

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

已知每个格子的边长都为1，请求出这些几何图形的凸包的周长。

输入输出格式

输入格式：

第一行包含一个正整数n(1<=n<=20)，表示几何图形的个数。

第二行包含n个字符，从左往右依次表示每个图形，“S”表示正方形，“C”表示圆形，“T”表示等边三角形。

输出格式：

输出一行一个实数，即凸包的周长。与答案的绝对或相对误差不超过10^-6时被认为是正确的。

输入输出样例

输入样例#1： 

4 TSTC

输出样例#1： 

9.088434417

解决步骤：

     我将计算分为了三个部分：底边、侧边和顶边，分别对应下图中的红色、橙色和绿色部分。

    ①计算凸包底边长度

        我们定义凸包和网格底边的重合部分为凸包的底边，那么对于凸包的左右两端只有三种情况：圆在最左/右边，正方形在最左/右边和圆在最左/右边。

    根据凸包的定义，对于这3种情况，凸包的底边显然会是下图中的红色部分：


     如果这几种图形凸包的右端，那也是同样道理。观察发现，对于若干个题中所说的图形组合，底边长可以分成下图中的橙色、紫色两段。其中橙色部分的长度

所以计算底边的代码：

//shape[i]为第i个位置上的图案，0=三角形，1=正方形，2=圆形
double btmspec[]={0.5,0.5,0};//对应三角形、正方形、圆形
double bottom=(n-1)+btmspec[shape[0]]+btmspec[shape[n-1]];

    ②计算侧边长

        如图，左右两端的图形的橙色部分长度加起来就是凸包的侧边长了。

        

//shape的意义同上
double lrspec[]={1,1.5,PI/2.0}
double side=lrspec[shape[0]]+lrspec[shape[n-1]];

    ③计算顶边

        这算是最难的一部分了。如果图形两端是正三角形，由于它的高度是

找最左边的不为三角形的图形位置：

int findLT(){
for(int i=0;i if(shape[i]!=TRIANGLE)
return i;
}

    找右端的同理。现在重点来了：假设最左端的不为三角形的位置为

    对于绿色部分的长度，我们分两种情况讨论：

        1.如果是三角形和正方形组合，中间夹着若干三角形，那么我们直接可以根据勾股定理得到斜边长

        2.如果是三角形和圆组合，中间夹着若干三角形，那么总长就是下图中橙色的斜边+一小段红色圆弧的长度。

    对于这种情况，我们如下计算：

由切线、圆和直角三角形的几何性质可知：

这就是计算凸包周长的步骤了，完整代码如下：

#include
using namespace std;
const int TRI=1,SQR=2,CIR=3;
int n,tcount=0,shape[21];//tcount为三角形数量，用于特判全是三角形的情况
double PI=3.14159265358979,SQ1_3=0.13397459621556,HS3_1=0.36602540378443;
double btmspec[]={0,0.5,0.5,0},lrspec[]={0,1,1.5,PI/2.0};
//SQ1_3=1-√3/2 HS3_1=(√3-1)/2
int findLT(){for(int i=0;iint findRT(){for(int i=n-1;i>=0;i--)if(shape[i]!=TRI)return i;}
double procHy(int slot1,int slot2){//处理顶边的长度
if(slot1==slot2)return 0;//最左/最右并没有三角形，直接跳过
int sh2=shape[slot2];//由之前讲的可以知道，这时shape[slot1]只能是三角形
double deltaX=abs(slot1-slot2);
if(sh2==SQR){//正方形和三角形组合
deltaX-=0.5;
return sqrt(SQ1_3*SQ1_3+deltaX*deltaX)+0.5;
}else{//sh2一定为CIRCLE
double hyd=sqrt(deltaX*deltaX+HS3_1*HS3_1);
double alpha=acos(0.5/hyd),theta=acos(HS3_1/hyd);
return hyd*sin(alpha)+(theta-alpha)*0.5;
}
}
int main(){
cin>>n;
for(int i=0,x=0;i do{x=getchar();}while(x<'A'||x>'Z');
if(x=='C')shape[i]=CIR;
if(x=='S')shape[i]=SQR;
if(x=='T')shape[i]=TRI,tcount++;
}
double ans=0;
ans+=(n-1)+btmspec[shape[0]]+btmspec[shape[n-1]];//bottom
ans+=lrspec[shape[0]]+lrspec[shape[n-1]];//left&right
//top
if(tcount==n)ans+=n-1;//特判全是三角形的情况
else{
int lt=findLT(),rt=findRT();//找最左和最右不是三角形的位置
ans+=(rt-lt)+procHy(0,lt)+procHy(n-1,rt);
}
printf("%.8lf",ans);
return 0;
}