CDOJ1600-矩形切割（2017 UESTC Training for Data Structures P）

迈不过友情╰ 2022-06-13 09:19 117阅读 0赞

**传送门：[CDOJ1600][]**

**题目大意：**

在一个二维平面坐标系上给你n个矩形，求n个矩形并集的面积，矩形平行坐标轴

**题目思路：**

这题很好想到的是扫描线做，但是这题n只有100.所以可以用一种很简单的方法来做

矩形切割，即从最后一个往上找，如果与他有相交部分就递归的把矩形分成几部分

来求解没有相交的部分，是一种暴力的方法，复杂度是n\*n 但是因为有递归部分，

所以常数可能会有点大，但是对于n=100还是够了

对于矩形切割详见该博客：[矩形切割][Link 1]  代码还是很好理解的

**AC代码：**

#include<bits/stdc++.h>
    using namespace std;
    
    struct st
    {
        double x1,y1,x2,y2;
    }s[205];
    double sum[205];
    int n;
    
    void sove(double x1,double y1,double x2,double y2,int x,int k)
    {
        while(k<n&&(x1>=s[k].x2||x2<=s[k].x1||y1>=s[k].y2||y2<=s[k].y1))k++;
        if(k>=n)
        {
            sum[x]+=(x2-x1)*(y2-y1);
            return ;
        }
        if(x1<s[k].x1)
        {
            sove(x1,y1,s[k].x1,y2,x,k+1);
            x1 = s[k].x1;
        }
        if(x2>s[k].x2)
        {
            sove(s[k].x2,y1,x2,y2,x,k+1);
            x2 = s[k].x2;
        }
        if(y1<s[k].y1)
        {
            sove(x1,y1,x2,s[k].y1,x,k+1);
            y1 = s[k].y1;
        }
        if(y2>s[k].y2)
        {
            sove(x1,s[k].y2,x2,y2,x,k+1);
            y2 = s[k].y2;
        }
    }
    
    int main()
    {
        while(cin>>n,n)
        {
            for(int i=0;i<n;i++)scanf("%lf%lf%lf%lf",&s[i].x1,&s[i].y1,&s[i].x2,&s[i].y2),sum[i] = 0;
            double ans = 0;
            for(int i=n-1;i>=0;i--)
            {
                sove(s[i].x1,s[i].y1,s[i].x2,s[i].y2,i,i+1);
            }
            for(int i=0;i<n;i++)
                ans+=sum[i];
            printf("%.2lf\n",ans);
        }
        return 0;
    }

[CDOJ1600]: http://acm.uestc.edu.cn/#/problem/show/1600
[Link 1]: http://blog.csdn.net/ACdreamers/article/details/8777920