the problem is at first complicated, but once you hold the concept of 2d array prefix and 2d difference array you will find↵
it simple, first you have to swap coordinates such that x1<x2 and y1<y2 and after that you construct the difference array such that each rectangle is filled with a bunch of nonzero numbers , then you construct the 2d prefix array, finally we count all zero's in the prefix where 0 means not surrounded by a rectangle and any non zero number indicates the opposite↵
↵
#include <bits/stdc++.h>↵
#include <algorithm>↵
using namespace std;↵
#define fre freopen("input.txt","r",stdin); freopen("output.txt","w",stdout)↵
#define read(t) ll t; cin>>t↵
#define reads(s) string s; cin>>s↵
#define Fast ios_base::sync_with_stdio(false);cin.tie(NULL)↵
#define once solve()↵
#define much(t) ll t; cin>>t; while(t--)solve()↵
#define el '\n'↵
#define ll long long↵
#define vl(v,n) vector<ll>v(n)↵
#define yes cout<<"YES"<<el↵
#define no cout<<"NO"<<el↵
#define ins(vec,n) vector<ll>vec(n);for(auto&i:vec)cin>>i↵
#define all(s) s.begin(),s.end()↵
#define up(i,a,n) for(ll i=a;i<n;i++)↵
#define down(i,a,n) for(ll i=a;i>=n;i--)↵
#define put(v) for(auto i:v) cout<<i<<' '; cout<<el↵
#define put2d(v) up(i,0,v.size()){ up(j,0,v[i].size()){cout<<v[i][j]<<' ';} cout<<el;}↵
#define putpair(v) for(auto i:v)cout<<"("<<i.first<<","<<i.second<<") "; cout<<el↵
const int Max = 200007;↵
const int MOD = 1000000007;↵
ll tc = 1;↵
void solve() {↵
read(w); read(h); read(n);↵
vector<vector<ll>>diffArr(w+1,vector<ll>(h+1,0));↵
vector<vector<ll>>prefix(w+1,vector<ll>(h+1,0));↵
while(n--) {↵
read(x1);read(y1);read(x2);read(y2);↵
if (x1 > x2)swap(x1, x2);↵
if (y1 > y2)swap(y1, y2);↵
diffArr[x1-1][y1-1] += 1;↵
diffArr[x2][y1-1] -= 1;↵
diffArr[x1-1][y2] -= 1;↵
diffArr[x2][y2] += 1;↵
}↵
up(i,1,w+1){↵
up(j,1,h+1){↵
prefix[i][j]=diffArr[i-1][j-1]+prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1];↵
}↵
}↵
ll cnt{};↵
up(i,1,w+1){↵
up(j,1,h+1){↵
if(prefix[i][j]==0)cnt++;↵
}↵
}↵
cout<<cnt<<el;↵
}↵
↵
int main() {↵
Fast;↵
#ifndef ONLINE_JUDGE↵
fre;↵
#endif↵
if(tc){much(t);}↵
else {once;}↵
return 0;↵
}
it simple, first you have to swap coordinates such that x1<x2 and y1<y2 and after that you construct the difference array such that each rectangle is filled with a bunch of nonzero numbers , then you construct the 2d prefix array, finally we count all zero's in the prefix where 0 means not surrounded by a rectangle and any non zero number indicates the opposite↵
↵
#include <algorithm>↵
using namespace std;↵
#define fre freopen("input.txt","r",stdin); freopen("output.txt","w",stdout)↵
#define read(t) ll t; cin>>t↵
#define reads(s) string s; cin>>s↵
#define Fast ios_base::sync_with_stdio(false);cin.tie(NULL)↵
#define once solve()↵
#define much(t) ll t; cin>>t; while(t--)solve()↵
#define el '\n'↵
#define ll long long↵
#define vl(v,n) vector<ll>v(n)↵
#define yes cout<<"YES"<<el↵
#define no cout<<"NO"<<el↵
#define ins(vec,n) vector<ll>vec(n);for(auto&i:vec)cin>>i↵
#define all(s) s.begin(),s.end()↵
#define up(i,a,n) for(ll i=a;i<n;i++)↵
#define down(i,a,n) for(ll i=a;i>=n;i--)↵
#define put(v) for(auto i:v) cout<<i<<' '; cout<<el↵
#define put2d(v) up(i,0,v.size()){ up(j,0,v[i].size()){cout<<v[i][j]<<' ';} cout<<el;}↵
#define putpair(v) for(auto i:v)cout<<"("<<i.first<<","<<i.second<<") "; cout<<el↵
const int Max = 200007;↵
const int MOD = 1000000007;↵
void solve() {↵
read(w); read(h); read(n);↵
vector<vector<ll>>diffArr(w+1,vector<ll>(h+1,0));↵
vector<vector<ll>>prefix(w+1,vector<ll>(h+1,0));↵
while(n--) {↵
read(x1);read(y1);read(x2);read(y2);↵
if (x1 > x2)swap(x1, x2);↵
if (y1 > y2)swap(y1, y2);↵
diffArr[x1-1][y1-1] += 1;↵
diffArr[x2][y1-1] -= 1;↵
diffArr[x1-1][y2] -= 1;↵
diffArr[x2][y2] += 1;↵
}↵
up(i,1,w+1){↵
up(j,1,h+1){↵
prefix[i][j]=diffArr[i-1][j-1]+prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1];↵
}↵
}↵
ll cnt{};↵
up(i,1,w+1){↵
up(j,1,h+1){↵
if(prefix[i][j]==0)cnt++;↵
}↵
}↵
cout<<cnt<<el;↵
}↵
↵
int main() {↵
#ifndef ONLINE_JUDGE↵
fre;↵
#endif↵
else {once;}↵
return 0;↵
}
