10 条题解
-
3
Bill_Yang LV 10 @ 2017-07-09 17:08:46
本题可使用部分搜索+计算几何（半平面交）的方法AC
搜索直线划分凸多边形的顺序O(9!)，再使用半平面交计算划分部分的面积（nlogn，n为半平面交计算的点数），再按照题意判断。具体步骤：
1.将凸多边形拆成直线，加入直线队列
2.（剪枝）如果当前面积已经比答案小，return
3.搜索加入一个未被使用的直线，使用半平面交计算面积。
4.如果半平面交面积now和剩余部分面积last-now在题目范围内，还原原来的信息。
5.如果半平面交面积now比剩余部分面积last-now小，翻转当前直线的方向向量，重新求一次半平面交。因为边搜边半平面交，所以可以使剪枝发挥更大的作用。
还有注意题目要卡精度，如果最后一个点过不到，加一个dcmp试试。代码：
#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<complex> #include<vector> #include<cstdio> #include<cmath> #include<map> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } const double eps=1e-8; int DoubleCompare(double x) { if(fabs(x)<eps)return 0; //=0 else if(x<0)return -1; //<0 else return 1; //>0 } struct Point { double x,y; Point() {} Point(double _x,double _y):x(_x),y(_y) {} Point operator + (const Point& a) const { return Point(x+a.x,y+a.y); } Point operator - (const Point& a) const { return Point(a.x-x,a.y-y); } Point operator * (const double a) const { return Point(x*a,y*a); } bool operator < (Point b) const { return x<b.x||(x==b.x&&y<b.y); } } P[105],La[105],Lb[105]; double Dist(Point a,Point b) { //欧几里得距离 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } typedef Point Vector; double Cross(Vector a,Vector b) { //叉积 return a.x*b.y-b.x*a.y; } double Area(Point a,Point b,Point c) { //三点的平行四边形有向面积 Vector u=b-a,v=c-a; return Cross(u,v); } double Area(int n,Point* P) { //计算多边形有向面积（剖分法） double ans=0; for(int i=2; i<n; i++)ans+=Area(P[1],P[i],P[i+1]); return ans/2; } struct Line { //有向直线（参数方程表示），左边为半平面 Point p; //直线上任意一点 Vector v; //方向向量 double ang; Line() {} Line(Point p,Vector v):p(p),v(v) { ang=atan2(v.y,v.x); } bool operator < (const Line& L) const { return ang<L.ang; } } l[105],lr[105]; bool OnLeft(Line L,Point p) { //判断点p是否在有向直线L左边（若不舍直线上的点则加上等号） return DoubleCompare(Cross(L.v,L.p-p))>0; } Point GetIntersection(Line a,Line b) { //求直线交点 Vector u=a.p-b.p; double t=Cross(u,b.v)/Cross(a.v,b.v); return a.p+a.v*t; } int HalfplaneIntersection(int n,Line* L,Point* poly) { //半平面相交O(nlogn) sort(L+1,L+n+1); //极角排序 int first=1,last=1; Point p[n+5]; Line q[n+5]; q[last]=L[1]; for(int i=2; i<=n; i++) { while(first<last&&!OnLeft(L[i],p[last-1]))last--; while(first<last&&!OnLeft(L[i],p[first]))first++; q[++last]=L[i]; if(fabs(Cross(q[last].v,q[last-1].v))<eps) { //平行同向，可以舍一个，取内侧 last--; if(!OnLeft(L[i],p[last-1]))q[last]=L[i]; } if(first<last)p[last-1]=GetIntersection(q[last-1],q[last]); //求出交点 } while(first<last&&!OnLeft(q[first],p[last-1]))last--; //删除无用平面 if(last-first<=1)return 0; //相交把平面交成了空集 p[last]=GetIntersection(q[last],q[first]); int m=0; for(int i=first; i<=last; i++)poly[++m]=p[i]; return m; //返回交的点数 引用传递交的端点 } int n,m,vst[105],cnt; double delta,Ans=0,last,now; Point ans[105]; void Dfs(int Depth) { if(last<=Ans)return; if(Depth==m+1) { Ans=last; return; } Line tmp[105]; int tcnt=cnt,Last=last; memcpy(tmp,l,sizeof(l)); for(int i=1; i<=m; i++) if(!vst[i]) { vst[i]=1; l[++cnt]=lr[i]; //加入直线 cnt=HalfplaneIntersection(cnt,l,ans); //求交 now=Area(cnt,ans); memcpy(l,tmp,sizeof(tmp)); if(DoubleCompare(fabs(last-now-now)-delta)<=0) { cnt=tcnt; now=last; } else if(DoubleCompare(last-now-now)>0) { cnt=tcnt; Line ltmp=Line(Lb[i],Lb[i]-La[i]); //向量翻转 l[++cnt]=ltmp; //加入直线 cnt=HalfplaneIntersection(cnt,l,ans); //求交 now=Area(cnt,ans); for(int i=1; i<cnt; i++)l[i]=Line(ans[i],ans[i]-ans[i+1]); l[cnt]=Line(ans[cnt],ans[cnt]-ans[1]); } else { for(int i=1; i<cnt; i++)l[i]=Line(ans[i],ans[i]-ans[i+1]); l[cnt]=Line(ans[cnt],ans[cnt]-ans[1]); } last=now; Dfs(Depth+1); vst[i]=0; memcpy(l,tmp,sizeof(tmp)); cnt=tcnt; last=Last; } } int main() { cin>>n; for(int i=1; i<=n; i++)cin>>P[i].x>>P[i].y; cin>>m; for(int i=1; i<=m; i++) { Point a,b; cin>>a.x>>a.y>>b.x>>b.y; La[i]=a,Lb[i]=b; lr[i]=Line(a,a-b); } cin>>delta; for(int i=1; i<n; i++)l[i]=Line(P[i],P[i]-P[i+1]); l[cnt=n]=Line(P[n],P[n]-P[1]); last=Area(n,P); Dfs(1); printf("%0.5lf\n",Ans); return 0; }Accepted
状态 耗时 内存占用
#1 Accepted 3ms 256.0KiB
#2 Accepted 3ms 256.0KiB
#3 Accepted 3ms 256.0KiB
#4 Accepted 3ms 276.0KiB
#5 Accepted 6ms 332.0KiB
#6 Accepted 53ms 256.0KiB
#7 Accepted 68ms 332.0KiB
#8 Accepted 213ms 256.0KiB
#9 Accepted 118ms 372.0KiB
#10 Accepted 3ms 256.0KiB -
2
#include<iostream> #include<cmath> #include<cstdio> using namespace std; typedef struct{ double x; double y; }node; int n; double delta,maxarea; int s[10];int d[9];int s1[10][10],s2[10][10]; node u[9],v[9]; node t[10][30]; node t1[10][10][30],t2[10][10][30]; double diff(node a,node b,node c){ return (b.y-a.y)*(c.x-a.x)-(b.x-a.x)*(c.y-a.y); } node cross(node a,node b,node c,node d){ node ans; if(fabs(a.x-b.x)<1e-9){ double k,t; k=(d.y-c.y)/(d.x-c.x); t=c.y-k*c.x; ans.x=a.x; ans.y=a.x*k+t; } else{ double k,t; k=(b.y-a.y)/(b.x-a.x); t=a.y-k*a.x; if(fabs(c.x-d.x)<1e-9){ ans.x=c.x; ans.y=c.x*k+t; } else{ double kk,tt; kk=(d.y-c.y)/(d.x-c.x); tt=c.y-kk*c.x; ans.x=(tt-t)/(k-kk); ans.y=ans.x*k+t; } } return ans; } void deal(int i,int j){ int l,k,m,p=0; double differ; bool check=true; node f,g; for(l=0;l<s[i];++l){ differ=diff(u[j],v[j],t[i][l]); if(fabs(differ)<1e-9)continue; if(differ<0){ if(p>0){ check=false; break; } p=-1; } else{ if(p<0){ check=false; break; } p=1; } } if(check){ s1[i][j]=s[i]; for(l=0;l<=s[i];++l)t1[i][j][l]=t[i][l]; s2[i][j]=0; return; } for(l=0;l<s[i];++l) if(diff(u[j],v[j],t[i][l])*diff(u[j],v[j],t[i][l+1])<1e-9)break; for(k=l+1;k<s[i];++k) if(diff(u[j],v[j],t[i][k])*diff(u[j],v[j],t[i][k+1])<1e-9)break; f=cross(u[j],v[j],t[i][l],t[i][l+1]); g=cross(u[j],v[j],t[i][k],t[i][k+1]); s1[i][j]=s2[i][j]=1; t1[i][j][0]=f; for(m=l+1;m<=k;++m)t1[i][j][s1[i][j]++]=t[i][m]; t1[i][j][s1[i][j]++]=g; t1[i][j][s1[i][j]]=f; t2[i][j][0]=g; for(m=k+1;m<s[i];++m)t2[i][j][s2[i][j]++]=t[i][m]; for(m=0;m<=l;++m)t2[i][j][s2[i][j]++]=t[i][m]; t2[i][j][s2[i][j]++]=f; t2[i][j][s2[i][j]]=g; } double area(int n,node *t){ int i; double s=0; for(i=2;i<n;++i)s+=diff(t[0],t[i-1],t[i]); return fabs(s); } void dfs(int i){ int j; double a1[10],a2[10]; bool check=true; for(j=0;j<n;++j) if(!d[j]){ deal(i,j); a1[j]=area(s1[i][j],t1[i][j]); a2[j]=area(s2[i][j],t2[i][j]); if(fabs(a1[j]-a2[j])<delta+1e-9)d[j]=i+1; } for(j=0;j<n;++j) if(!d[j]){ check=false; d[j]=i+1; int l; if(a1[j]>a2[j]){ s[i+1]=s1[i][j]; for(l=0;l<=s[i+1];++l)t[i+1][l]=t1[i][j][l]; } else{ s[i+1]=s2[i][j]; for(l=0;l<=s[i+1];++l)t[i+1][l]=t2[i][j][l]; } if(max(a1[j],a2[j])>maxarea)dfs(i+1); d[j]=0; } if(check) maxarea=area(s[i],t[i]); for(j=0;j<n;++j) if(d[j]==i+1)d[j]=0; } int main(){ int i; scanf("%d",&s[0]); for(i=0;i<s[0];++i)scanf("%lf%lf",&t[0][i].x,&t[0][i].y); t[0][s[0]]=t[0][0]; scanf("%d",&n); for(i=0;i<n;++i) scanf("%lf%lf%lf%lf",&u[i].x,&u[i].y,&v[i].x,&v[i].y); scanf("%lf",&delta); dfs(0); printf("%.5lf\n",maxarea/2); return 0; }
Bill_Yang
LV 10
@ 2017-07-09 17:08:46
- 1
