一道神奇的计算几何题
前置芝士
推导公式
对于一串是圆和正方形开头和结尾时是十分好做的,这里也不展开了.
那么问题来了,三角形开头时需要怎么算呢???
如果全部都是三角形那也可以直接算,一串三角形后面是一个正方形:
可以将这条红色线段树放入一个三角形中,其中一条边为黄色线段树,这个还是十分好计算的(l=n-0.5)(n为三角形个数),还有一条边为正方形边长减去绿色线段(正三角形的高),(l=1-sqrt{3}*0.5),这样,这道题的差不多一半的分就被拿到了.
对于这样一条线段,如果又用刚才的方法那真是太天真了,这样会导致计算上出现一点小小的偏差,但是绝对能把您卡掉,红色线段与圆是相切的,所以:
可以通过这样算出红色线段的长,但是,在红色线段上那小小的圆弧要怎么办呢
(高倍放大镜下的图),将这个角分成几个角,用三角函数求出弧度,再求出弧长就好了(因为作者懒,具体不解释).
具体做法
实在是看见三角函数就头痛,所以pass了.
代码
#include<bits/stdc++.h>
#define rap(i,first,last) for(int i=first;i<=last;++i)
#define pi 3.1415926535
using namespace std;
int N;
double answer,sum,Long;
char s[100];
double Helf(char ch)
{
if(ch=='S')return 2.0;
if(ch=='C')return pi/2;
if(ch=='T')return 1.5;
}
double Delta(double a,double b)
{
double CosA,Angle,c;
c=sqrt(a*a+b*b);
CosA=b/c;
Angle=acos(CosA)/pi*180;
return Angle;
}
double Delta_2(double a,double b)
{
double CosA,Angle,c;
c=sqrt(b*b-a*a);
CosA=(2*b*b-2*a*a)/(2*b*c);
Angle=acos(CosA)/pi*180;
return Angle;
}
int main()
{
scanf("%d",&N);
rap(i,1,N)cin>>s[i];
answer=N*2-2;
int l=1,r=N;
while(s[l]=='T'&&l<N)l++;
while(s[r]=='T'&&r>1)r--;
if(l>r)//特判全是三角形
{
answer=N*2+1;
printf("%.9ld",answer);
return 0;
}
if(l==1)
answer+=Helf(s[1]);//第一个位置不是三角形
else
{
Long=l-1;
if(s[l]=='C')
{
sum=Delta(sqrt(3)*0.5-0.5,Long)+Delta_2(
sqrt((sqrt(3)*0.5-0.5)*(sqrt(3)*0.5-0.5)+Long*Long-0.25),
sqrt((sqrt(3)*0.5-0.5)*(sqrt(3)*0.5-0.5)+Long*Long));//算出圆弧的角度,如果看不懂可以先学习三角函数
answer+=1+sqrt((sqrt(3)*0.5-0.5)*(sqrt(3)*0.5-0.5)+Long*Long-0.25)-(Long-0.5)+(90-sum)/360*pi;//算出圆弧加线段的长
}
else
answer+=+1+sqrt((1-0.5*sqrt(3))*(1-0.5*sqrt(3))+(Long-0.5)*(Long-0.5))-(Long-1);//正方形的计算还是比较简单的
}
if(r==N)//以下同理
answer+=Helf(s[N]);
else
{
Long=N-r;
if(s[r]=='C')
{
sum=Delta(sqrt(3)*0.5-0.5,Long)+Delta_2(
sqrt((sqrt(3)*0.5-0.5)*(sqrt(3)*0.5-0.5)+Long*Long-0.25),
sqrt((sqrt(3)*0.5-0.5)*(sqrt(3)*0.5-0.5)+Long*Long));
answer+=1+sqrt((sqrt(3)*0.5-0.5)*(sqrt(3)*0.5-0.5)+Long*Long-0.25)-(Long-0.5)+(90-sum)/360*pi;
}
else
answer+=+1+sqrt((1-0.5*sqrt(3))*(1-0.5*sqrt(3))+(Long-0.5)*(Long-0.5))-(Long-1);
}
printf("%.9ld",answer);
}