gym 101620 L Lunar Landscape

54 阅读 0 评论 36 点赞

我是靠谱客的博主疯狂白猫，最近开发中收集的这篇文章主要介绍gym 101620 L Lunar Landscape，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意

给定两类正方形，一类正放一类斜45度放，题面给出n个正方形，求平面覆盖的面积

题解

对于正放的正方形直接二维差分求前缀和即可，对于第二类，可以旋转坐标系，利用 $x_0=x-y,y_0=x+y$ 来表示，之后对于旋转后的坐标轴进行差分求前缀和，最后统计答案的时候，对于每个点首先判断其是否被第一类覆盖，覆盖则加1。之后判断其是否被第二类坐标系覆盖，通过上述转化继续调整坐标系，之后判断调整后映射到原坐标系的区域时候被加过1，若没加过则加0.25

代码

/**
*
author:
TelmaZzzz
*
create:
2019-10-29-14.35.03
**/
#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>
//#include <random>
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
//#pragma comment(linker,"/STACK:10240000,10240000")
//mt19937 rand_(time(0));
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);}//ÄæÔª
//int head[N],NEXT[M],ver[M],tot;void link(int u,int v){ver[++tot]=v;NEXT[tot]=head[u];head[u]=tot;}
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();
//ios::sync_with_stdio(false);
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;
//cout<<x<<' '<<y<<endl;
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;
}
}
}
//cout<<f[0+N][1+N]<<" "<<g[+2*N][0+N]<<endl;
//W(ans);
//cout<<(sizeof(mpA)+sizeof(mpB)+sizeof(f)+sizeof(g))/1024/1024<<endl;
printf("%.2fn",ans);
//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
return 0;
}