首页 > 代码库 > bzoj4948: World Final2017 A
bzoj4948: World Final2017 A
求简单多边形内的最长线段长度
显然存在一组最优解,使其所在直线经过多边形的两个端点,枚举这两个端点,求出直线和多边形的有效交点,从而得出直线有哪些部分在多边形内(含边界)。
由于多边形的一些边可能与直线重合,求交需要一些分类讨论。
#include<bits/stdc++.h>typedef long long i64;typedef double ld;struct pos{ int x,y; ld abs(){return sqrt(i64(x)*x+i64(y)*y);}}ps[211];pos operator-(const pos&a,const pos&b){return (pos){a.x-b.x,a.y-b.y};}i64 operator*(const pos&a,const pos&b){return i64(a.x)*b.y-i64(a.y)*b.x;}int sgn(i64 x){return x<0?-1:x>0;}int n,t[211],kp;ld ans=0,ks[211];void maxs(ld&x,ld y){if(x<y)x=y;}#define F(a) ps[a]*ps[a+1]/ld(p*(ps[a+1]-ps[a]))*plvoid chk(pos p){ kp=0; ld pl=p.abs(); for(int i=0;i<n+5;++i)t[i]=sgn(p*ps[i]); for(int i=0,z;i<n;++i)if(t[i]&&t[i]!=t[i+1]){ for(z=i+1;!t[z];++z); if(t[z]!=t[i]){ if(z-i<3)ks[kp++]=F(i); else{ ld a0=F(i),a1=F(z-1); ks[kp++]=(a0<a1)==(t[i]>0)?a0:a1; } }else if(z-i==3){ ld a0=F(i),a1=F(z-1); if((a0<a1)==(t[i]>0))maxs(ans,fabs(a1-a0)); } } std::sort(ks,ks+kp); for(int i=0;i<kp;i+=2)maxs(ans,ks[i+1]-ks[i]);}int main(){ scanf("%d",&n); for(int i=0;i<n;++i)scanf("%d%d",&ps[i].x,&ps[i].y); for(int i=0;i<n;++i){ pos o=ps[i]; for(int j=0;j<n;++j)ps[j]=ps[j]-o; for(int j=0;j<5;++j)ps[n+j]=ps[j]; for(int j=i+1;j<n;++j)chk(ps[j]); } printf("%.8f",ans); return 0;}
bzoj4948: World Final2017 A
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。