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[];
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<?-:x>;}
int n,t[],kp;
ld ans=,ks[];
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]))*pl
void chk(pos p){
kp=;
ld pl=p.abs();
for(int i=;i<n+;++i)t[i]=sgn(p*ps[i]);
for(int i=,z;i<n;++i)if(t[i]&&t[i]!=t[i+]){
for(z=i+;!t[z];++z);
if(t[z]!=t[i]){
if(z-i<)ks[kp++]=F(i);
else{
ld a0=F(i),a1=F(z-);
ks[kp++]=(a0<a1)==(t[i]>)?a0:a1;
}
}else if(z-i==){
ld a0=F(i),a1=F(z-);
if((a0<a1)==(t[i]>))maxs(ans,fabs(a1-a0));
}
}
std::sort(ks,ks+kp);
for(int i=;i<kp;i+=)maxs(ans,ks[i+]-ks[i]);
}
int main(){
scanf("%d",&n);
for(int i=;i<n;++i)scanf("%d%d",&ps[i].x,&ps[i].y);
for(int i=;i<n;++i){
pos o=ps[i];
for(int j=;j<n;++j)ps[j]=ps[j]-o;
for(int j=;j<;++j)ps[n+j]=ps[j];
for(int j=i+;j<n;++j)chk(ps[j]);
}
printf("%.8f",ans);
return ;
}
上一篇:MySql foreach属性


下一篇:CS0433: 类型“BasePage”同一时候存在于“c:\Windows\Microsoft.NETxxxxxxxxxxxxxxxx