P3680 凸轮廓线

一道神奇的计算几何题

• 前置芝士

  1.正三角形,正方形,圆:什么,您都会,那真是太好了.
  2.三角函数的运用:因为我不是很想在这一块写太多,具体可以自行百度.

• 推导公式

  对于一串是圆和正方形开头和结尾时是十分好做的,这里也不展开了.
  那么问题来了,三角形开头时需要怎么算呢???
  如果全部都是三角形那也可以直接算,一串三角形后面是一个正方形:
  
  可以将这条红色线段树放入一个三角形中,其中一条边为黄色线段树,这个还是十分好计算的\(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);
}

P3680 凸轮廓线

原文：https://www.cnblogs.com/Sxy_Limit/p/12178891.html