首页 > 代码库 > 【计算几何】【分类讨论】Gym - 101173C - Convex Contour
【计算几何】【分类讨论】Gym - 101173C - Convex Contour
注意等边三角形的上顶点是卡不到边界上的。
于是整个凸包分成三部分:左边的连续的三角形、中间的、右边的连续的三角形。
套个计算几何板子求个三角形顶点到圆的切线、三角形顶点到正方形左上角距离啥的就行了,分类比较多。
#include<cstdio> #include<cmath> using namespace std; const double PI=acos(-1.0); int n; char a[25]; struct Point{ double x,y; double length(){ return sqrt(x*x+y*y); } }; typedef Point Vector; Vector operator - (const Point &a,const Point &b){ return (Vector){a.x-b.x,a.y-b.y}; } Vector operator + (const Vector &a,const Vector &b){ return (Vector){a.x+b.x,a.y+b.y}; } Vector operator * (const double &K,const Vector &v){ return (Vector){K*v.x,K*v.y}; } Vector Rotate(Vector A,double rad) { return (Vector){A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad)}; } Vector unit(Vector A){ double l=A.length(); return (Vector){A.x/l,A.y/l}; } double sqr(double x){ return x*x; } int main(){ scanf("%d%s",&n,a+1); bool alltr=1; for(int i=1;i<=n;++i){ if(a[i]!=‘T‘){ alltr=0; break; } } if(alltr){ printf("%d\n",2*n+1); } else{ double ans=0; int I,J; for(int i=1;i<=n;++i){ if(a[i]!=‘T‘){ if(i!=1){ if(a[i]==‘S‘){ ans+=((Point){0.5,sqrt(3.0)/2.0}-(Point){(double)(i-1),1.0}).length(); } else if(a[i]==‘C‘){ Vector v=(Point){(double)i-0.5,0.5}-(Point){0.5,sqrt(3.0)/2.0}; ans+=sqrt(sqr(v.length())-0.5*0.5); v=Rotate(v,asin(0.5/v.length())); Point p=(Point){0.5,sqrt(3.0)/2.0}+ans*unit(v); double xian=((Vector){(double)i-0.5,1.0}-p).length(); double jiao=acos((sqr(xian)-0.5*0.5*2.0)/(-2.0*0.5*0.5)); ans+=jiao*0.5; } } else{ if(a[i]==‘S‘){ ans+=2.0; } else if(a[i]==‘C‘){ ans+=PI*0.5; } } I=i; break; } } for(int j=n,i=1;j>=1;++i,--j){ if(a[j]!=‘T‘){ if(j!=n){ if(a[j]==‘S‘){ ans+=((Point){0.5,sqrt(3.0)/2.0}-(Point){(double)(i-1),1.0}).length(); } else if(a[j]==‘C‘){ Vector v=(Point){(double)i-0.5,0.5}-(Point){0.5,sqrt(3.0)/2.0}; double d=sqrt(sqr(v.length())-0.5*0.5); ans+=d; v=Rotate(v,asin(0.5/v.length())); Point p=(Point){0.5,sqrt(3.0)/2.0}+d*unit(v); double xian=((Vector){(double)i-0.5,1.0}-p).length(); double jiao=acos((sqr(xian)-0.5*0.5*2.0)/(-2.0*0.5*0.5)); ans+=jiao*0.5; } } else{ if(a[j]==‘S‘){ ans+=2.0; } else if(a[j]==‘C‘){ ans+=PI*0.5; } } J=j; break; } } if(I!=1 && J!=n){ ans+=((double)(I-1)+1.0); ans+=((double)(n-J)+1.0); ans+=(double)(J-I+1); if(a[I]==‘S‘ && a[J]==‘S‘){ ans+=(double)(J-I+1); } else if(a[I]==‘C‘ && a[J]==‘C‘){ ans+=(double)(J-I); } else{ ans+=((double)(J-I)+0.5); } } else if(I==1 && J==n){ ans+=(double)(n-1)*2.0; } else if(I==1 && J!=n){ ans+=((double)(n-J)+1.0); if(a[J]==‘S‘){ ans+=((double)J-0.5)*2.0; } else{ ans+=(((double)J-0.5)*2.0-0.5); } } else{ ans+=((double)(I-1)+1.0); if(a[I]==‘S‘){ ans+=((double)(n-I+1)-0.5)*2.0; } else{ ans+=(((double)(n-I+1)-0.5)*2.0-0.5); } } printf("%.11f\n",ans); } return 0; }
【计算几何】【分类讨论】Gym - 101173C - Convex Contour
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。