[ROIR 2023 Day 1] 扫地机器人 题解

· · 题解

比较简单的一个扫描线题。

对于每次指令分开考虑，它扫过的一个矩形的四个坐标是好求的。以 N 指令为例，令 x_0,y_0 为原来机器人的左下角坐标，d 为移动距离，那么扫过的矩形的两个 x 坐标分别为 x,x+k，两个 y 坐标分别为 y,y+d+k；其他指令可以类似地自行推导。

最后对于所有指令产生的矩形求面积并即可。

示例代码（使用了本人编写的模板库中的扫描线算法）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace IAOI_lib{
  class atlantis{
    typedef pair<int,int> pii;
    typedef tuple<int,int,int,int> tpi;
    private:
      struct Line{
        int l,r,h,s;
        bool operator <(const Line &x)const{
          return h<x.h;
        }
      };
      int n;
      vector<Line> L;
      vector<pii> B;
      vector<int> X,C,S;
      void build(int u,int l,int r){
        if(B[u]=make_pair(l,r);l==r)return;
        int m=l+r>>1;
        build(u<<1,l,m),build(u<<1|1,m+1,r);
        pushup(u);
      };
      void pushup(int u){
        if(C[u])S[u]=X[B[u].second+1]-X[B[u].first];
        else S[u]=S[u<<1]+S[u<<1|1];
      }
      void update(int u,int l,int r,int c){
        if(X[B[u].second+1]<=l||r<=X[B[u].first])return;
        if(l<=X[B[u].first]&&X[B[u].second+1]<=r)C[u]+=c;
        else update(u<<1,l,r,c),update(u<<1|1,l,r,c);
        pushup(u);
      }
      int all_prod(){return S[1];}
    public:
      int areas_union(vector<tpi> &a){
        X.resize(a.size()<<1),L.resize(a.size()<<1);
        for(int i=0;i<a.size();i++){
          auto &[xa,ya,xb,yb]=a[i];
          if(xa>xb)swap(xa,xb); if(ya>yb)swap(ya,yb);
          X[i<<1]=xa,X[i<<1|1]=xb;
          L[i<<1]=(Line){xa,xb,ya,1},L[i<<1|1]=(Line){xa,xb,yb,-1};
        }
        sort(L.begin(),L.end(),[](Line x,Line y){return x.h<y.h;});
        sort(X.begin(),X.end()),n=unique(X.begin(),X.end())-X.begin();
        B.resize(n<<2),C.resize(n<<2),S.resize(n<<3),build(1,0,n-2);
        int c=0;
        for(int i=0;i+1<a.size()<<1;i++){
          update(1,L[i].l,L[i].r,L[i].s);
          c+=all_prod()*(L[i+1].h-L[i].h);
        }
        return c;
      }
  };
} // 扫描线模板
main(){
  ios::sync_with_stdio(false);
  int k,n; cin>>k>>n;
  vector<tuple<int,int,int,int> > a;
  int x=0,y=0; a.emplace_back(0,0,k,k);
  while(n--){
    char c; int d; cin>>c>>d;
    switch(c){
      case 'N':a.emplace_back(x,y,x+k,y+d+k),y+=d; break;
      case 'E':a.emplace_back(x,y,x+d+k,y+k),x+=d; break;
      case 'W':a.emplace_back(x-d,y,x+k,y+k),x-=d; break;
      default:a.emplace_back(x,y-d,x+k,y+k),y-=d;
    }
  } // 依次处理每一条指令
  cout<<IAOI_lib::atlantis().areas_union(a)<<endl;
  return 0;
}