题意

https://www.luogu.org/problem/P3680


思考

拆点即可。

注意精度。


代码

 // luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
const ld eps=1E-;
const ld pi=acos(-);
const ld inf=1E9;
inline bool equal(ld x,ld y)
{
return abs(x-y)<=eps;
}
struct pt
{
ld x,y;
pt(ld a=,ld b=){x=a,y=b;}
pt operator+(const pt&A){return pt(x+A.x,y+A.y);}
pt operator-(const pt&A){return pt(x-A.x,y-A.y);}
pt operator*(ld d){return pt(x*d,y*d);}
pt operator/(ld d){return pt(x/d,y/d);}
ld operator*(const pt&A){return x*A.y-y*A.x;}
void out(){cout<<"("<<x<<","<<y<<")";}
};
struct line
{
pt A,B;
line(pt a=pt(),pt b=pt())
{
A=a,B=b;
}
};
inline int cross(pt A,pt B)
{
ld d=A*B;
if(equal(d,))
return ;
return d>?:-;
}
inline ld dis(pt A,pt B)
{
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
inline pt intersection(line a,line b)
{
pt A=b.B-b.A,B=a.B-a.A,C=b.A-a.A;
if(cross(A,B)==)
return pt(inf,inf);
ld d=-(B*C)/(B*A);
return b.A+A*d;
}
inline pt foot(pt A,line a)
{
return intersection(line(A,A+pt(a.B.y-a.A.y,a.A.x-a.B.x)),a);
}
inline bool seg(line a,line b)
{
return cross(a.A-b.A,b.B-b.A)*cross(a.B-b.A,b.B-b.A)==-&&
cross(b.A-a.A,a.B-a.A)*cross(b.B-a.A,a.B-a.A)==-;
}
pt O(,);
bool cmp(pt A,pt B)
{
ld x=atan2(A.y-O.y,A.x-O.x),y=atan2(B.y-O.y,B.x-O.x);
if(equal(x,y))
return dis(A,O)<dis(B,O);
return x<y;
}
vector<pt>convex(vector<pt>P)
{
int pos=;
for(int i=;i<P.size();++i)
if(P[i].x<P[pos].x)
pos=i;
swap(P[pos],P[]);
O=P[];
sort(P.begin()+,P.end(),cmp);
vector<pt>ans;
int now=;
for(int i=;i<P.size();++i)
{
while(now>&&cross(P[i]-ans[now-],ans[now-]-ans[now-])!=-)
ans.pop_back(),--now;
ans.push_back(P[i]);
++now;
}
return ans;
}
inline bool cmpLine(line a,line b)
{
return atan2(a.A.y-a.B.y,a.A.x-a.B.x)<atan2(b.A.y-b.B.y,b.A.x-b.B.x);
}
inline bool onClockwise(line a,line b,line c)//b,c的交点在a顺时针方向
{
return cross(intersection(b,c)-a.A,a.B-a.A)==;
}
inline bool isSame(line a,line b)
{
return cross(a.A-b.B,b.A-b.B)==;
}
line wait[];
vector<line>halfPlane(vector<line>A)
{
vector<line>ans;
sort(A.begin(),A.end(),cmpLine);
int l=,r=;
for(int i=;i<A.size();++i)
{
while(l<r&&!isSame(A[i],wait[r])&&onClockwise(A[i],wait[r-],wait[r]))
--r;
while(l<r&&!isSame(A[i],wait[l])&&onClockwise(A[i],wait[l],wait[l+]))
++l;
if(!isSame(A[i],wait[r])||r==)
wait[++r]=A[i];
else if(!onClockwise(wait[r],wait[r-],A[i]))
wait[r]=A[i];
}
while(l<r&&onClockwise(wait[l],wait[r],wait[r-]))
--r;
while(l<r&&onClockwise(wait[r],wait[l],wait[l+]))
++l;
for(int i=l;i<=r;++i)
ans.push_back(wait[i]);
return ans;
}
inline ld length(vector<pt>P)
{
ld sum=;
for(int i=;i<P.size();++i)
sum+=dis(P[i-],P[i]);
sum+=dis(P[P.size()-],P[]);
return sum;
}
const ld base=;
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
vector<pt>P;
for(int i=;i<=n;++i)
{
char ch;
cin>>ch;
ld x=i;
if(ch=='S')
{
P.push_back(pt(x,));
P.push_back(pt(x+,));
P.push_back(pt(x+,));
P.push_back(pt(x,));
}
else if(ch=='T')
{
P.push_back(pt(x,));
P.push_back(pt(x+,));
P.push_back(pt(x+0.5,sqrt()/));
}
else
{
for(ld j=;j<base;j+=)
{
ld ra=*pi/base*j;
P.push_back(pt(x+0.5+cos(ra)/,0.5+sin(ra)/));
}
}
}
ld ans=length(convex(P));
cout<<fixed<<setprecision()<<ans<<endl;
return ;
}

最新文章

  1. 自己动手写计算器v1.2
  2. c#泛型方法返回null的问题
  3. 在Apache下开启SSI配置支持include shtml html和快速配置服务器
  4. 【COGS1384】鱼儿仪仗队
  5. ScrollView 在嵌套 ViewPager 时出现的问题
  6. css3选择器:nth-child和nth-of-type之间的差别
  7. TensorFlow文档翻译-01-TensorFlow入门
  8. 使用 eclipse 的常用操作
  9. Zabbix 配置监控主机
  10. Mysql的跨表更新
  11. _luckdraw
  12. PostgreSQL Oracle 兼容性之 - sys_guid()
  13. for(var i=0;i&lt;=3;i++){ setTimeout(function() { console.log(i) }, 10);}
  14. 微信服务器配置令牌(Token)
  15. Vue-axios快速上手(转)
  16. 素数回文(hdu1431)
  17. DRF框架QQ登录功能
  18. Java 存储和读取 oracle CLOB 类型字段的实用方法
  19. ArduinoYun教程之OpenWrt-Yun与CLI配置Arduino Yun
  20. SpringMVC系列(十)&lt;mvc:default-servlet-handler/&gt;(处理静态资源)和&lt;mvc:annotation-driven /&gt;

热门文章

  1. 特殊字符,如Emoji表情Base64存储到数据库
  2. Rancher2.x部署K8s
  3. mac笔记本安装Android sdk
  4. T-SQL代码搜索
  5. 使用git pull拉取代码的时候,无法拉取最新代码,报&quot;unable to update local ref&quot;错误。
  6. $[NOIp2008]$双栈排序 栈/二分图/贪心
  7. 【一起学源码-微服务】Nexflix Eureka 源码十三:Eureka源码解读完结撒花篇~!
  8. Spring MVC 请求处理过程
  9. llinux重启、用户切换、注销命令
  10. schedule of 2016-10-24~2016-10-30(Monday~Sunday)——1st semester of 2nd Grade