矩形切割-面积求并

矩形切割-面积求并

离散化：将无限空间的有限个体映射到有限的空间上，做到逻辑上的有限和有序，避免重复。

学习矩形切割就不得不认识线段切割。进而和离散化扯上了关系。

关于线段切割：

设线段ab和cd有交集：k1k2

当a

当b>k2，ab分解（切割）成k2b

相关题目：

VIJOS 1165 火烧赤壁

​​#include #include using namespace std;struct edge{ int x1,x2;}eg[20005];int cmp(edge a,edge b){ return a.x1>n){ for(int i=0;ie) e=eg[i].x2; else if(eg[i].x1>=e){ L=L+e-s; s=eg[i].x1; e=eg[i].x2; } } if(n>0)L=L+e-s; printf("%d\n",L); } return 0;}

矩形切割：

X方向和Y方向分别进行分割。

X:

x1 (x1,y1)-(x3,y2)

x2>x4，S1矩形 -> (x4,y1)-(x2,y2)

Y:

y1 (x1,y1)-(x2,y3)

y2>y4，S2矩形 -> (x1,y3)-(x2,y2)

POJ 3695

​​#include using namespace std;struct node{ int x1,y1,x2,y2; int s;}rec[25];int a[25];int r;void cover(int x1,int y1,int x2,int y2,int k){ while(k=rec[a[k]].x2||x2<=rec[a[k]].x1||y1>=rec[a[k]].y2||y2<=rec[a[k]].y1)) k++; if(k>=r) { rec[a[k-1]].s+=(x2-x1)*(y2-y1); return ; } if(x1rec[a[k]].x2){ cover(rec[a[k]].x2,y1,x2,y2,k+1); x2=rec[a[k]].x2; } if(y1rec[a[k]].y2){ cover(x1,rec[a[k]].y2,x2,y2,k+1); y2=rec[a[k]].y2; }}int main(){ //freopen("cin.txt","r",stdin); int n,m; int t=0; while(cin>>n>>m&&(n+m)){ for(int i=0;i=0;i--){ cover(rec[a[i]].x1,rec[a[i]].y1,rec[a[i]].x2,rec[a[i]].y2,i+1); } int ans=0; for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。