询问第51行至54行
查看原帖
询问第51行至54行
511268
PIKA_PIKA楼主2021/7/30 11:34
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
typedef long long LL;
const int N = 2020;
vector<int> allx, ally;
map<int, int> mapx, mapy;
int f[N][4];
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2)
{
    b[x1][y1] ++;
    b[x2 + 1][y1] --;
    b[x1][y2 + 1] --;
    b[x2 + 1][y2 + 1] ++;
}
int main()
{
    int n; 
    cin >> n;
    allx.push_back(0);
    ally.push_back(0);
    for(int i = 0; i < n; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        f[i][0]=x1;
        f[i][2]=x2;
        f[i][1]=y1;
        f[i][3]=y2;
        allx.push_back(y1);
        allx.push_back(y2);
        ally.push_back(x1);
        ally.push_back(x2);
    }
    sort(allx.begin() + 1, allx.end());
    allx.erase(unique(allx.begin() + 1, allx.end()), allx.end());
    sort(ally.begin() + 1, ally.end());
    ally.erase(unique(ally.begin() + 1, ally.end()), ally.end());
    
    for(int i = 1; i < allx.size(); i++) mapx[allx[i]] = i;
    for(int i = 1; i < ally.size(); i++) mapy[ally[i]] = i;
    
    for(int i = 0; i < n; i++)
    {
        int x1, y1 , x2, y2;
        //老师课上放的代码,疑惑为什么要这么写
        x1 = f[i][3];
        y1 = f[i][0];
        x2 = f[i][1];
        y2 = f[i][2];
        
        insert(mapx[x1], mapy[y1], mapx[x2] - 1, mapy[y2] - 1);
    }
    
    for(int i = 1; i <= allx.size(); i++)
      for(int j = 1; j <= ally.size(); j++)
        a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];
        
        LL ans = 0;
        for(int i = 1; i <= allx.size(); i++)
          for(int j = 1; j <= ally.size(); j++)
            {
                if(a[i][j])
                {
                    int x1, y1, x2, y2;
                    x1 = allx[i];
                    y1 = ally[j];
                    x2 = allx[i + 1];
                    y2 = ally[j + 1];
                    ans += (LL)(x2 - x1) * (y2 - y1);
                }
            }
    cout << ans << endl;
    return 0;
}
2021/7/30 11:34
加载中...