题意
给定两类正方形，一类正放一类斜45度放，题面给出n个正方形，求平面覆盖的面积
题解
对于正放的正方形直接二维差分求前缀和即可，对于第二类，可以旋转坐标系，利用
x
0
=
x
−
y
,
y
0
=
x
+
y
x_0=x-y,y_0=x+y
x0=x−y,y0=x+y来表示，之后对于旋转后的坐标轴进行差分求前缀和，最后统计答案的时候，对于每个点首先判断其是否被第一类覆盖，覆盖则加1。之后判断其是否被第二类坐标系覆盖，通过上述转化继续调整坐标系，之后判断调整后映射到原坐标系的区域时候被加过1，若没加过则加0.25
代码
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <ctime>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
typedef double db
;
void _R(int &x
) { scanf("%d", &x
); }
void _R(ll
&x
) { scanf("%lld", &x
); }
void _R(db
&x
) { scanf("%lf", &x
); }
void _R(char &x
) { scanf(" %c", &x
); }
void _R(char *x
) { scanf("%s", x
); }
void R() {}
template<class T, class... U
> void R(T
&head
, U
&... tail
) { _R(head
); R(tail
...); }
void _W(const int &x
) { printf("%d", x
); }
void _W(const ll
&x
) { printf("%lld", x
); }
void _W(const db
&x
) { printf("%.16f", x
); }
void _W(const char &x
) { putchar(x
); }
void _W(const char *x
) { printf("%s", x
); }
template<class T> void _W(const vector
<T
> &x
) { for (auto i
= x
.begin(); i
!= x
.end(); _W(*i
++)) if (i
!= x
.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U
> void W(const T
&head
, const U
&... tail
) { _W(head
); putchar(sizeof...(tail
) ? ' ' : '\n'); W(tail
...); }
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define erp(x,y,z) for(int x=y;x>=z;x--)
#define PB push_back
#define MP make_pair
#define INF 1073741824
#define inf 1152921504606846976
#define pi 3.14159265358979323846
#define Fi first
#define Se second
const int N
=1550,M
=2e6;
const long long mod
=1e9+7;
inline int read(){int ret
=0;char ch
=getchar();bool f
=1;for(;!isdigit(ch
);ch
=getchar()) f
^=!(ch
^'-');for(;isdigit(ch
);ch
=getchar()) ret
=(ret
<<1)+(ret
<<3)+ch
-48;return f
?ret
:-ret
;}
ll
gcd(ll a
,ll b
){return b
?gcd(b
,a
%b
):a
;}
ll
ksm(ll a
,ll b
,ll mod
){int ans
=1;while(b
){if(b
&1) ans
=(ans
*a
)%mod
;a
=(a
*a
)%mod
;b
>>=1;}return ans
;}
ll
inv2(ll a
,ll mod
){return ksm(a
,mod
-2,mod
);}
void TelmaZzzz(){
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif
}
int mpA
[2*N
+2][2*N
+2];
int mpB
[4*N
+2][4*N
+2];
int f
[4*N
+2][4*N
+2];
int g
[4*N
+2][4*N
+2];
char c
[3];
void draw(int x
,int y
){
cout
<<f
[x
+N
][y
+N
]<<' '<<f
[x
+N
][y
+N
-1]<<' '<<g
[x
-y
+2*N
][x
+y
+N
]<<endl
;
cout
<<f
[x
-1+N
][y
-1+N
]<<' '<<f
[x
+N
][y
-1+N
]<<' '<<g
[x
-y
+2*N
][x
+y
-1+N
]<<endl
;
}
int main(){
TelmaZzzz();
int n
;
R(n
);
int x
,y
,d
;
rep(i
,1,n
){
R(c
,x
,y
,d
);
if(c
[0]=='A'){
mpA
[x
-d
/2+N
][y
-d
/2+N
]++;
mpA
[x
-d
/2+N
][y
+d
/2+N
]--;
mpA
[x
+d
/2+N
][y
-d
/2+N
]--;
mpA
[x
+d
/2+N
][y
+d
/2+N
]++;
}
else {
int xx
=x
-y
,yy
=x
+y
;
x
=xx
,y
=yy
;
mpB
[x
-d
/2+2*N
][y
-d
/2+2*N
]++;
mpB
[x
-d
/2+2*N
][y
+d
/2+2*N
]--;
mpB
[x
+d
/2+2*N
][y
-d
/2+2*N
]--;
mpB
[x
+d
/2+2*N
][y
+d
/2+2*N
]++;
}
}
rep(i
,1,2*N
){
rep(j
,1,2*N
){
f
[i
][j
]=f
[i
-1][j
]+f
[i
][j
-1]-f
[i
-1][j
-1]+mpA
[i
][j
];
}
}
rep(i
,1,4*N
){
rep(j
,1,4*N
){
g
[i
][j
]=g
[i
-1][j
]+g
[i
][j
-1]-g
[i
-1][j
-1]+mpB
[i
][j
];
}
}
db ans
=0.0;
rep(i
,-1520,1520){
rep(j
,-1520,1520){
if(f
[i
+N
][j
+N
]) ans
+=1.0;
x
=i
-j
;
y
=i
+j
;
if(g
[x
+2*N
][y
+2*N
]){
if(!f
[i
+N
][j
+N
]) ans
+=0.25;
if(!f
[i
+N
][j
-1+N
]) ans
+=0.25;
}
if(g
[x
+2*N
][y
-1+2*N
]){
if(!f
[i
-1+N
][j
-1+N
]) ans
+=0.25;
if(!f
[i
+N
][j
-1+N
]) ans
+=0.25;
}
}
}
printf("%.2f\n",ans
);
return 0;
}
