USACO2012 overplanting /// 矩阵切割递归 oj21547

题目大意：

在农场的任何一个“轴向对齐”的长方形区域（即垂直和水平方向）种植草坪。

现种植了N（1≤ N ≤10）个不同的矩形区域，其中一些甚至可能重叠。

Input

Multiple test cases. For each case:

* Line 1: The integer N.

* Lines 2..1+N: Each line contains four space-separated integers x₁y₁x₂y₂ specifying a rectangular region with upper-left corner (x₁, y₁) and lower-right corner (x₂, y₂). All coordinates are in the range -10,000...10,000.

Output

For each case, output one line: The total area covered by grass.

Sample Input

2
0 5 4 1
2 4 6 2

Sample Output

用矩形切割的方法看代码就懂

#include <bits/stdc++.h>

using namespace std;

int x1[],x2[],m1[],m2[],sum;

void cur(int len1,int len2,int hig1,int hig2,int i)

{

    if(len1>=len2||hig1<=hig2) return;

    while(i>=&&(len1>=x2[i]||hig1<=m2[i]||len2<=x1[i]||hig2>=m1[i]))

        i--;

    if(i<)

    {

        sum+=(len2-len1)*(hig1-hig2);

        return;

    }

    if(len1<x1[i])

    {

        cur(len1,x1[i],hig1,hig2,i-);

        len1=x1[i];

    }

    if(len2>x2[i])

    {

        cur(x2[i],len2,hig1,hig2,i-);

        len2=x2[i];

    }

    if(hig1>m1[i])

    {

        cur(len1,len2,hig1,m1[i],i-);

        hig1=m1[i];

    }

    if(hig2<m2[i])

    {

        cur(len1,len2,m2[i],hig2,i-);

        hig2=m2[i];

    }

    return;

}

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        sum=;

        for(int i=;i<n;i++)

            scanf("%d%d%d%d",&x1[i],&m1[i],&x2[i],&m2[i]);

        for(int i=;i<n;i++)

            cur(x1[i],x2[i],m1[i],m2[i],i-);

        printf("%d\n",sum);

    }

    return ;

}

巴特西

USACO2012 overplanting /// 矩阵切割递归 oj21547

最新文章

热门文章

巴特西

USACO2012 overplanting /// 矩阵切割 递归 oj21547

最新文章

热门文章

USACO2012 overplanting /// 矩阵切割递归 oj21547