C++の長方形エリアII

（軸に沿った）長方形のリストがあるとします。ここで、各rectangle [i] ={x1、y1、x2、y2}です。ここで、（x1、y1）は左下隅のポイントであり、（x2、y2）は右上隅のポイントです。 i番目の長方形。

平面内のすべての長方形でカバーされる総面積を見つける必要があります。答えは非常に大きい可能性があるため、モジュロ10 ^ 9+7を使用できます。

したがって、入力が次のような場合

その場合、出力は6になります。

これを解決するには、次の手順に従います-

• m =10 ^ 9 + 7

• 関数add（）を定義します。これには、a、b、

  が必要です。

• return（（a mod m）+（b mod m）mod m）

• 1つの関数を定義して圧縮します。これには2次元行列v

  が必要です。

• アレイの温度を定義する

• 初期化i：=0の場合、i

  • tempの最後にv[i、0]を挿入します

  • tempの最後にv[i、2]を挿入します

• 配列の温度を並べ替える

• 1つのマップを定義します。ret

• idx：=0

• 初期化i：=0の場合、i

  • temp [i]がretのメンバーでない場合、-

    • ret [temp [i]]：=idx

    • （idxを1増やします）

• retを返す

• メインの方法から、次のようにします-

• 配列xvを定義する

• xvの最後に{0}を挿入します

• 初期化i：=0の場合、i

  • xvの最後にv[i、0]を挿入します

  • xvの最後にv[i、2]を挿入します

• 配列xvを並べ替える

• uniItr=xvの一意の要素を持つリストの最初の要素

• xvからuniItrを削除します

• 1つのマップインデックスを定義する

• idx：=0

• 初期化i：=0の場合、i

  • index [xv [i]]：=i

• インデックスサイズと同じサイズの配列カウントを定義します

• 1つの2D配列xを定義します

• 初期化i：=0の場合、i

  • x1：=v [i、0]、y1：=v [i、1]

  • x2：=v [i、2]、y2：=v [i、3]

  • xの最後に{y1、x1、x2、1}を挿入します

  • xの最後に{y2、x1、x2、-1}を挿入します

• 配列x

  を並べ替えます

• ret：=0

• 合計：=0、currentY：=0

• 初期化i：=0の場合、i

  • y：=x [i、0]

  • x1：=x [i、1]、x2：=x [i、2]

  • sig：=x [i、3]

  • ret：=add（ret、（y-currentY）* sum）

  • currentY：=y

  • 初期化i：=index [x1]の場合、i

    • count [i]：=count [i] + sig

  • 合計：=0

  • 初期化i：=0の場合、i <カウントのサイズの場合、更新（iを1増やします）、実行-

    • count [i]> 0の場合、

      • 合計：=合計+（xv [i + 1] --xv [i]）

• return ret mod m

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
class Solution {
   public:
   lli add(lli a, lli b){
      return ((a % m) + (b % m) % m);
   }
   map<int, int> compress(vector<vector<int> >& v){
      vector<int> temp;
      for (int i = 0; i < v.size(); i++) {
         temp.push_back(v[i][0]);
         temp.push_back(v[i][2]);
      }
      sort(temp.begin(), temp.end());
      map<int, int> ret;
      int idx = 0;
      for (int i = 0; i < temp.size(); i++) {
         if (!ret.count(temp[i])) {
            ret[temp[i]] = idx;
            idx++;
         }
      }
      return ret;
   }
   int rectangleArea(vector<vector<int> >& v){
      vector<int> xv;
      xv.push_back({ 0 });
      for (int i = 0; i < v.size(); i++) {
         xv.push_back(v[i][0]);
         xv.push_back(v[i][2]);
      }
      sort(xv.begin(), xv.end());
      vector<int>::iterator uniItr = unique(xv.begin(), xv.end());
      xv.erase(uniItr, xv.end());
      map<int, int> index;
      int idx = 0;
      for (int i = 0; i < xv.size(); i++) {
         index[xv[i]] = i;
      }
      vector<int> count(index.size());
      vector<vector<int> > x;
      int x1, x2, y1, y2;
      for (int i = 0; i < v.size(); i++) {
         x1 = v[i][0];
         y1 = v[i][1];
         x2 = v[i][2];
         y2 = v[i][3];
         x.push_back({ y1, x1, x2, 1 });
         x.push_back({ y2, x1, x2, -1 });
      }
      sort(x.begin(), x.end());
      lli ret = 0;
      lli sum = 0, currentY = 0;
      for (int i = 0; i < x.size(); i++) {
         lli y = x[i][0];
         x1 = x[i][1];
         x2 = x[i][2];
         int sig = x[i][3];
         ret = add(ret, (y - currentY) * sum);
         currentY = y;
         for (int i = index[x1]; i < index[x2]; i++) {
            count[i] += sig;
         }
         sum = 0;
         for (int i = 0; i < count.size(); i++) {
            if (count[i] > 0) {
               sum += (xv[i + 1] - xv[i]);
            }
         }
      }
      return ret % m;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,0,2,2},{1,0,2,3},{1,0,3,1}};
   cout << (ob.rectangleArea(v));
}

入力

{{0,0,2,2},{1,0,2,3},{1,0,3,1}}

出力

6