题目大意：矩形面积并。
题目思路：矩形切割。
[cpp] #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define inf 0x3f3f3f3f #define uint unsigned __int64 #define M 10000 struct node { double p1[2],p2[2]; }a[M],now; int total; int judge(node a,node b) { for(int i=0;i<2;i++) { if(a.p2[i]<=b.p1[i]||a.p1[i]>=b.p2[i]) return 0; } return 1; } void cut(node tmp) { int k1,k2; for(int i=0;i<2;i++) { k1=max(tmp.p1[i],now.p1[i]); k2=min(tmp.p2[i],now.p2[i]); if(tmp.p1[i] { a[++total]=tmp; a[total].p2[i]=k1; } if(tmp.p2[i]>k2) { a[++total]=tmp; a[total].p1[i]=k2; } tmp.p1[i]=k1; tmp.p2[i]=k2; } } int main() { int n,i,j,count=1; while(scanf("%d",&n),n) { total=0; for(i=1;i<=n;i++) { scanf("%lf%lf%lf%lf",&now.p1[0],&now.p1[1],&now.p2[0],&now.p2[1]); for(j=total;j>=1;j--) { if(judge(now,a[j])) { cut(a[j]); a[j]=a[total--]; } } a[++total]=now; } double sum=0.0; for(i=1;i<=total;i++) sum+=(a[i].p2[0]-a[i].p1[0])*(a[i].p2[1]-a[i].p1[1]); printf("Test case #%d\n",count++); printf("Total explored area: %.2lf\n",sum); puts(""); } }