差不多是凸包的板子题,十(fei)分(chang)的(du)水(liu)。。。
40pts做法:
将矩形的四点,三角形的三点,圆形的上下两端各一点加入点阵,用 Andrew 算法求凸包即可。
对于圆出现在队列某一段的情况,要特别判断。
100pts做法:
其实只需要将40pts做法做两个改动即可:
-
1,将程序中的\(\pi\)设为3.141598653(这一步对步骤2至关重要);
-
2,仔细想想,题目中可能会出现 "CT" 或 "TC" 的情况。这时将三角形顶端与圆形顶端相连显然不对。
该题的 \(n\leqslant20\) 使我们考虑使用最蠢的办法:将圆上的数万个点加入点阵。
即使不会三角函数(比如本蒟蒻),用勾股定理将这些点的坐标算出来也比较简单。
加入的点数不能太少,也不能太多。点太少会有精度误差,太多可能会有几个点TLE。
时间复杂度为 \(O(n log(n))\) 。
下面是我的源代码:
#include <bits/stdc++.h>
#define ll long long
#define rgi register int
using namespace std;
const int M=1e7+7;
inline int read(){
int w=0,r=1;char c=getchar();
while(!(isdigit(c)||c=='0'))c=getchar();
if(c=='-')r=-1,c=getchar();
while(isdigit(c))w=w*10+c-'0',c=getchar();
return w*r;
}
int n,m,used[M],stk[M],cnt;
char c[M];
double pi=3.141592653,x,ans;
struct pt{
double x,y;
}p[M];
void add(double x,double y){
p[++m]=(pt){x,y};
}
bool operator <(pt aa,pt bb){
return aa.x<bb.x||(aa.x==bb.x&&aa.y<bb.y);
}
pt operator -(pt aa,pt bb){
return (pt){aa.x-bb.x,aa.y-bb.y};
}
double operator *(pt aa,pt bb){
return aa.x*bb.y*1.000000000-bb.x*aa.y*1.000000000;
}
double d(int x,int y){
return (double)sqrt(fabs(p[x].x-p[y].x)*fabs(p[x].x-p[y].x)*1.000000000+fabs(p[x].y-p[y].y)*fabs(p[x].y-p[y].y)*1.000000000);
}
int main(){
n=read();
scanf("%s",c+1);
if(n==1){
if(c[1]=='C')printf("%f\n",pi);
else if(c[1]=='S')printf("%f\n",4.000000000);
else if(c[1]=='T')printf("%f\n",3.000000000);
return 0;
}
for(int i=1;i<=n;i++,x+=1.000000000){
if(c[i]=='C'){
//if(i==1||i==n){
// ans=ans-1.000000000+pi/2.000000000;
//}
//add(x+0.500000000,0.000000000),add(x+0.500000000,1.000000000);
for(double j=0.000000000;j<=1.000000000;j+=0.000100000){
double xx=sqrt(0.250000000-fabs(j-0.500000000)*fabs(j-0.500000000)),x1=x+0.500000000-xx,x2=x+0.500000000+xx;
add(x1,j),add(x2,j);
}
}else if(c[i]=='S'){
add(x,0.000000000),add(x,1.000000000);
add(x+1.000000000,0.000000000),add(x+1.000000000,1.000000000);
}else{
add(x,0.000000000),add(x+1.000000000,0.000000000);
add(x+0.500000000,(double)sqrt(0.750000000));
}
}
sort(p+1,p+m+1);
stk[++cnt]=1;
for(int i=2;i<=m;i++){
while(cnt>=2&&(p[stk[cnt]]-p[stk[cnt-1]])*(p[i]-p[stk[cnt]])<=0.000000)used[stk[cnt--]]=0;
used[stk[++cnt]=i]=1;
}
int dn=cnt;
for(int i=m-1;i;i--)if(!used[i]){
while(cnt>=2&&(p[stk[cnt]]-p[stk[cnt-1]])*(p[i]-p[stk[cnt]])<=0.000000)used[stk[cnt--]]=0;
used[stk[++cnt]=i]=1;
}
for(int i=1;i<=cnt;i++){
int a=stk[i],b=stk[(i%cnt)+1];
ans+=d(a,b)*1.000000000;
}
printf("%.9lf\n",ans);
return 0;
}
/*
4
TSTC
*/