首页 > 代码库 > 求凸包
求凸包
BZOJ2829
#include <cstdio> #include <algorithm> #include <cmath> #define LDB long double using namespace std; const LDB eps=1e-8; struct data{ LDB x,y,alp; }tmp[1000001],a[1000001],sta[1000010]; int n,cnt; LDB xmini,ymini,bb,aa,r,ang[4],stddis; inline data operator - (const data&a,const data&b) {return (data){a.x-b.x,a.y-b.y,a.alp};} LDB X(data a,data b){ return(a.x*b.y-a.y*b.x); } LDB dis(data a,data b){ return(sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))); } int mycomp(const data&aa,const data&b){ if (aa.alp<b.alp-eps) return(1); if (aa.alp>b.alp+eps) return(0); return(dis(a[1],aa)>dis(a[1],b)); } void makepoint(LDB x,LDB y,LDB ag){ for (int i=0;i<4;i++){ tmp[++cnt].x=x+stddis*cos(ang[i]+ag); tmp[cnt].y=y+stddis*sin(ang[i]+ag); } } int main(){ freopen("a.in","r",stdin); freopen("wrong.out","w",stdout); scanf("%d",&n); scanf("%Lf%Lf%Lf",&bb,&aa,&r);aa-=2*r;bb-=2*r; ang[0]=atan2(bb,aa),ang[1]=atan2(bb,-aa),ang[2]=atan2(-bb,-aa),ang[3]=atan2(-bb,aa); stddis=sqrt(aa*aa/4+bb*bb/4); for (int i=1;i<=n;i++){ LDB t1,t2,t3; scanf("%Lf%Lf%Lf",&t1,&t2,&t3); makepoint(t1,t2,t3); } n=4*n; xmini=1e9,ymini=1e9; int po; for (int i=1;i<=n;i++){ if (ymini>tmp[i].y||(ymini==tmp[i].y&&tmp[i].x<xmini)){ xmini=tmp[i].x;ymini=tmp[i].y; po=i; } } data t=tmp[po];tmp[po]=tmp[1];tmp[1]=t; for (int i=2;i<=n;i++) tmp[i].alp=atan2(tmp[i].y-ymini,tmp[i].x-xmini); a[1].x=xmini;a[1].y=ymini; sort(tmp+2,tmp+n+1,mycomp); cnt=1; tmp[1].alp=-1e9; for (int i=2;i<=n;i++) if (tmp[i].alp!=tmp[i-1].alp) a[++cnt]=tmp[i]; n=cnt; int top=0; for (int i=1;i<=n;i++){ while (top>=2&&X(sta[top]-sta[top-1],a[i]-sta[top-1])<-eps) top--; sta[++top]=a[i]; } LDB ans=acos(-1)*2*r; for (int i=1;i<=top;i++) ans+=dis(sta[i],sta[i%top+1]); printf("%.2Lf\n",ans); }
求凸包
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。