题解 P3680 【[CERC2016]凸轮廓线 Convex Contour】
如果您渴望O(N)的优秀算法，请出门左转Sxy_Limit的题解；
如果您不会凸包，请先AC二维凸包板子；
如果您喜爱暴力，请看本人题解；
如果您时间紧迫，请直接看下面。
首先忽略NOI/NOI+/CTSC的难度
然后读题：给你一团边长为1的正方形、直径为1的圆、底为1的等边三角形，求凸包周长
接着思考：能否把图形化为点阵呢？然后直接求凸包？
答案是：没错，可以
但是不免会很暴力但是数据小的可怜
构造点阵的方法：
-
S（正方形），很简单，加4个点：左上 右上 左下 右下
-
T（三角形），和正方形同样简单（不过要用到勾股定理+一元一次方程算出三角形的高），加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:三角形
*///这是个好习惯