Atlantis

矩形面积并

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=2222;
#define lson i*2,l,m
#define rson i*2+1,m+1,r
#define root 1,1,k-1
double X[MAXN];
struct node
{
  double l,r,h;
  int d;
  node(){}
  node(double a,double b,double c,int d): l(a),r(b),h(c),d(d){}
  bool operator <(const node &b)const
  {
    return h<b.h;                    //扫描线排序
  }
}nodes[MAXN];
int cnt[MAXN*4];                     //线段树记录y轴扫描线在x轴区间内的数量
double sum[MAXN*4];                  //线段树记录x轴区间内的长度
void PushDown(int i,int l,int r)     //下传
{
  int m=(l+r)/2;
  if(cnt[i]!=-1)
  {
    cnt[i*2]=cnt[i*2+1]=cnt[i];      //父节点赋值给左右儿子
    sum[i*2]= (cnt[i]?(X[m+1]-X[l]):0) ;                    //父节点非零，l-mid的X轴长度记录在左儿子
    sum[i*2+1]= (cnt[i]?(X[r+1]-X[m+1]):0) ;
  }
}
void PushUp(int i) //上传
{
  if(cnt[i*2]==-1 || cnt[i*2+1]==-1)                        //左右儿子有-1上传父节已更新
    cnt[i]=-1;
  else if(cnt[i*2] != cnt[i*2+1])   //左右儿子不相同上传父节已更新
    cnt[i]=-1;
  else                              //如果左右节点未更新且不相同，直接合并上传到父节点
    cnt[i]=cnt[i*2];                //左儿子赋值给父节点
  sum[i]=sum[i*2]+sum[i*2+1];       //更新父节点
}
void build(int i,int l,int r)
{
  if(l==r)
  {
    cnt[i]=0;
    sum[i]=0;
    return ;
  }
  int m=(l+r)/2;
  build(lson);
  build(rson);
  PushUp(i);
}
void update(int ql,int qr,int v,int i,int l,int r)
{
  if(ql<=l && r<=qr)                //ql、qr区间覆盖l、r
  {
    if(cnt[i]!=-1)
    {
      cnt[i]+=v;                    //增加或减少一条Y轴扫描线
      sum[i] = (cnt[i]? (X[r+1]-X[l]):0);                     //上位边添加面积，下位边不添加
      return ;
    }
  }
  PushDown(i,l,r);
  int m=(l+r)/2;
  if(ql<=m) update(ql,qr,v,lson);
  if(m<qr) update(ql,qr,v,rson);
  PushUp(i);
}
int bin(double key,int n,double d[])
{
  int l=1,r=n;
  while(r>=l)
  {
    int m=(r+l)/2;                  //二分查找寻找该区域的左右区间，返回X的索引
    if(d[m]==key)
      return m;
    else if(d[m]>key)
      r=m-1;
    else
      l=m+1;
  }
  return -1;
}
int main()
{
  int q;
  int kase=0;
  while(scanf("%d",&q)==1&&q)       //矩形个数，只要输入成功就重复循环，0退出
  {
    int n=0,m=0;
    for(int i=1;i<=q;i++)           //读取矩形的四个参数
    {
      double x1,y1,x2,y2;
      scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
      X[++n]=x1;
      nodes[++m]=node(x1,x2,y1,1);
      X[++n]=x2;
      nodes[++m]=node(x1,x2,y2,-1);
    }
    sort(X+1,X+n+1);                //x坐标排序
    sort(nodes+1,nodes+m+1); //
    int k=1;                        //共k个不同的x坐标,组成了k-1个不同的区域
    for(int i=2;i<=n;i++)
      if(X[i]!=X[i-1]) X[++k]=X[i];
    build(1,1,k-1);                 //初始化两个数组，与下两行的作用一样，但是下面的全部初始化浪费时间
    //memset(cnt,0,sizeof(cnt) );
    //memset(sum,0,sizeof(sum) );
    double ret=0.0;                 //最终面积
    for(int i=1;i<m;i++)
    {
      int l=bin(nodes[i].l,k,X);
      int r=bin(nodes[i].r,k,X)-1;
      if(l<=r) update(l,r,nodes[i].d,root);
      ret += sum[1]*(nodes[i+1].h-nodes[i].h);                //总面积ret+=当前矩形宽度*(扫描线2的高度-扫描线1的高度)
    }
    printf("Test case #%d\nTotal explored area: %.2lf\n\n",++kase,ret );
  }
}

笔记：扫描线算法就是通过Y轴的扫描线从低到高扫过所有的矩形，上位边就入边，下位线就出线，再乘以当前区间的高度（扫描线2的高度-扫描线1的高度）