題目：Atlantis

?

我的上一篇文章已經講明了線段切割的思想，矩形切割就是把線段切割從一維推到二維就行了，思想都一樣。

#include <stdio.h> #include <string.h>const int N = 205;typedef struct {double x1,y1;double x2,y2;double sum; }Node;Node T[N];int n;void Cover(double x1,double y1,double x2,double y2,int k,int c) {while(k<n&&(x1>=T[k].x2||x2<=T[k].x1||y1>=T[k].y2||y2<=T[k].y1)) k++;if(k>=n){T[c].sum+=(x2-x1)*(y2-y1);return;}if(x1<T[k].x1){Cover(x1,y1,T[k].x1,y2,k+1,c);x1=T[k].x1;}if(x2>T[k].x2){Cover(T[k].x2,y1,x2,y2,k+1,c);x2=T[k].x2;}if(y1<T[k].y1){Cover(x1,y1,x2,T[k].y1,k+1,c);y1=T[k].y1;}if(y2>T[k].y2){Cover(x1,T[k].y2,x2,y2,k+1,c);y2=T[k].y2;} }int main() {int i,k=1;while(~scanf("%d",&n),n){for(i=0;i<n;i++){scanf("%lf%lf%lf%lf",&T[i].x1,&T[i].y1,&T[i].x2,&T[i].y2);T[i].sum=0;}for(i=n-1;i>=0;i--)Cover(T[i].x1,T[i].y1,T[i].x2,T[i].y2,i+1,i);double ans=0;for(i=0;i<n;i++)ans+=T[i].sum;printf("Test case #%d\n",k++);printf("Total explored area: %.2lf\n\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ1151(矩形切割入门题)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。