自动搬运

查看原文

来自洛谷，原作者为

	QwQcOrZ AFOed | 印刷成文不能代表它们就是真理 | 极东魔术昼寝结社之夏 | The Great Gig In The Sky

搬运于2025-08-24 21:51:32，当前版本为作者最后更新于2019-03-08 19:46:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

如果您渴望O(N)的优秀算法，请出门左转Sxy_Limit的题解；

如果您不会凸包，请先AC二维凸包板子；

如果您喜爱暴力，请看本人题解；

如果您时间紧迫，请直接看下面。

首先忽略NOI/NOI+/CTSC的难度

然后读题：给你一团边长为1的正方形、直径为1的圆、底为1的等边三角形，求凸包周长

接着思考：能否把图形化为点阵呢？然后直接求凸包？

答案是：没错，可以

但是不免会很暴力但是数据小的可怜

构造点阵的方法：

1. S（正方形），很简单，加4个点：左上 右上 左下 右下

2. T（三角形），和正方形同样简单（不过要用到勾股定理+一元一次方程算出三角形的高），加3个点：左下 右下 中间

3. C（正圆形），比较麻烦，可能有些人比如我会认为只要加圆中间最上和最下的点就够了。

大错特错！！！

可以试着输入：

2
CT

这样程序就会爆炸

为什么呢？

因为ta出现了一堆三角形+一个圆的情况，显然，三角形的顶点与圆中间最上方直接连一条线是很愚蠢的。

so，ta们的凸包上面部分就只能是一条直线加一小段圆弧

如何解决呢？

我们不能用一堆三角函数来搞出这条线的长度，因为那个我不会啊违反暴力出奇迹的原则。

也不能打表，因为我懒打这么多显然是不现实的。

自然是用最暴力的方法，把圆上的点几乎全部加到点阵里。

于是我们得出了以下结论：

 半径：r
 角度：a
 圆点坐标：(x0,y0)
 圆上任一点为：(x1,y1)
 x1=x0+r*cos(a*π/180)
 y1=y0+r*sin(a*π/180)

其中r=0.5（显然），a需要我们枚举，x0，y0也很容易知道

然后全部加进凸包就ok了

为了避免加入不必要的点，我们只加一坨三角形和一个圆中的这个圆的靠近三角形的一边加入圆上的一堆点。

然后特判两边的圆，直接跑凸包，就AC了

简单介绍一下我用的凸包：用两个单调栈，把凸包上半部分算出来，再把下半部分算出来，然后拼起来，就是整个凸包了

注意加点时重点的情况

还有就是由于凸包是自己构造的，所以就不需要sort了

详见代码：

#include<bits/stdc++.h>
#define sqr(x) x*x  //手动定义平方 
#define calc(i,j) (a[i].x!=a[j].x?(a[i].y-a[j].y)/(a[i].x-a[j].x):INT_MAX)  //计算斜率，凸包的内容 
using namespace std;
const int N=222222;  //定常数是个好习惯 
const double pi=3.1415926535;  //圆周率，背到这位就差不多了 
const double R=0.5;  //圆的半径 

struct R
{
    double x,y;
}a[N];  //存点 
int m,n=0,w[N],c[N],t1=1,t2=1,l,r;
string s;

inline void add(double x,double y)
{
    a[++n].x=x;
    a[n].y=y;
}
inline void Input_Structure()  //输入&构造，与凸包模板就差这里（重点！咚咚咚敲黑板） 
{
    scanf("%d",&m); 
    cin>>s;
    s=' '+s;  //习惯（pascal后遗症，经常忽略s[0]） 
    for (int i=1;i<=m;i++)  //找左边第一个要搞的圆 
    {
        if (s[i]=='C') l=i;
        if (s[i]!='T') break;
    }
    for (int i=m;i>0;i--)  //找右边第一个要搞的圆 
    {
        if (s[i]=='C') r=i;
        if (s[i]!='T') break;
    }
    r=r==m?0:r;  //特判最左端的圆 
    l=l==1?0:l;  //特判最右端的圆 
    for (int i=1;i<=m;i++)  //线性扫描 
    {
        if (s[i]=='S')  //正方形 
        {
            add(i,0);
            add(i,1);
            add(i+1,0);
            add(i+1,1);
        }
        if (s[i]=='T')  //三角形 
        {
            if (a[n-1].x!=i||a[n-1].y!=0) add(i,0);  //避免重点 
            add(i+0.5,sqrt(0.75));  //根据勾股定理：0.5^2+x^2=1^2 => 0.25+x^2=1 => x^2=1-0.25 => x=sqrt(1-0.25) 
            add(i+1,0);
        }
        if (s[i]=='C')  //圆 
        {
            if (l==i) for (double j=40;j>0;j-=0.001) add(i+R-R*sin(j*pi/180),R+R*cos(j*pi/180));  //如果是左端的要搞的 
            add(i+0.5,0);
            if (r==i) for (double j=0;j<40;j+=0.001) add(i+R+R*sin(j*pi/180),R+R*cos(j*pi/180));  //如果是右端的要搞的 
                 else add(i+0.5,1);  //如果不是右端要搞的点（理论上来说可以去掉） 
        }
    }
}
inline void TB1()  //计算凸包上半部分，不展开讲了，不是重点 
{
    w[1]=1;
    for (int i=2;i<=n;i++)
    {
        while (t1>1&&calc(w[t1-1],w[t1])>calc(w[t1],i)) t1--;
        w[++t1]=i;
    }
}
inline void TB2()  //计算凸包下半部分，不展开讲了，不是重点
{
    c[1]=1;
    for (int i=2;i<=n;i++)
    {
        while (t2>1&&calc(c[t2-1],c[t2])<calc(c[t2],i)) t2--;
        c[++t2]=i;
    }
}

int main()
{
    Input_Structure(); 
    TB1();
    TB2();
    double ans=0;
    for (int i=1;i<t1;i++) ans+=sqrt(sqr(fabs(a[w[i]].x-a[w[i+1]].x))+sqr(fabs(a[w[i]].y-a[w[i+1]].y)));
    for (int i=1;i<t2;i++) ans+=sqrt(sqr(fabs(a[c[i]].x-a[c[i+1]].x))+sqr(fabs(a[c[i]].y-a[c[i+1]].y)));
    if (s[1]=='C') ans=ans-1+pi/2;  //特判最左端的圆，显然凸包不是一条直线 
    if (s[m]=='C') ans=ans-1+pi/2;  //特判最右端的圆，显然凸包不是一条直线 
    printf("%.9lf\n",ans);

    return 0;
}
/*
S:正方形
C:正圆形
T:三角形
*///这是个好习惯