HDU - 1542 扫描线入门+线段树离散化

时间：2022-06-20 15:28:44

扫描线算法+线段树维护简介：

像这种求面积的并集的题目，就适合用扫描线算法解决，具体来说就是这样

类似这种给出点的矩形的对角的点的坐标，然后求出所有矩形面积的交集的问题，可以采用扫描线算法解决。图如下，我们要求红色部分的面积：

HDU - 1542 扫描线入门+线段树离散化

我们可以通过一条叫扫描线的东西解决问题。具体来说：

我们首先给自己一条线，这条可以我称之为标准线(棕色线表示)

HDU - 1542 扫描线入门+线段树离散化

从上往下（从下往上也行）我们把每个矩形用一个四元组表示了l,r,h,f  也就是说，把一个矩形用上下两条边表示，l,r分别是x1,x2，而h则是y坐标，f代表这条线是顶边还是低边。

这样就把信息存储下来。

需要注意的一点是，由于线段树维护区间的时候，会存在区间过大的清空，因此我们需要对x坐标进行去重排序，从而达到把点进行离散化，但是这里我们需要注意的是，我们这里维护区间，而线段树是从维护点，进而维护区间的，因此我们可以这样，把区间的左下标表示为区间，比如[0-3]区间，我们可以转化为点0，代表0-1，1代表1-2，2代表2-3。这样我们再找左端点的时候，我们之间用坐标代替，而右端点，则需要查找到下标后，减一即可。

维护总的区间的和，用高度差乘以区间和，就是面积，每次维护，求出面积，就是如上图所示的样子，从下往上不断求出面积。

#include<iostream>

#include<stdio.h>

#include<algorithm>

#include<string.h>

using namespace std;

inline int L(int r){return r<<;};

inline int R(int r){return r<<|;};

inline int MID(int l,int r){return (l+r)>>;};

const int maxx = ;

struct segment{

  double l,r,h;

  int f;

}ss[maxx*];

struct node{

  int l,r,cnt;

  double len;

}tree[maxx<<];

double pos[maxx*];

int nums;

bool cmp(segment p,segment q)

{

    return p.h<q.h;

}

void build(int root,int l,int r)

{

    tree[root].l=l;

    tree[root].r=r;

    tree[root].cnt=;

    tree[root].len=;

    if (l==r)

        return;

    int mid = MID(tree[root].l,tree[root].r);

    build(L(root),l,mid);

    build(R(root),mid+,r);

}

void get_len(int root)

{

    if (tree[root].cnt)//不是0 代表已经被整段覆盖

        tree[root].len = pos[tree[root].r+] - pos[tree[root].l];

    else if (tree[root].l == tree[root].r)//只是一个点

        tree[root].len = ;

    else

        tree[root].len = tree[L(root)].len + tree[R(root)].len;

}

void update(int root,int l,int r,int val)

{

    if (tree[root].l == l && tree[root].r == r)

    {

        tree[root].cnt += val;

        get_len(root);

        return;

    }

    int mid = (tree[root].l + tree[root].r)>>;

    if (r<=mid)

       update(L(root),l,r,val);

    else if (l > mid)

        update(R(root),l,r,val);

    else {

        update(L(root),l,mid,val);

        update(R(root),mid+,r,val);

    }

   get_len(root);

}

int binary(double key,int low,int high)

{

   // cout<<key<<endl;

    int mid;

     while(low<=high)

     {

         mid = MID(low,high);

         if (pos[mid]==key)

             return mid;

         else if (key < pos[mid])

            high = mid-;

         else

            low = mid+;

     }

     return -;

}

int main(){

  int Case = ;

  int n;

  while(scanf("%d",&n)!=EOF && n)

  {

      nums=;

      for (int i=;i<n;i++){

        double x1,y1,x2,y2;

        scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);

        //记录下边

        ss[nums].l = x1;

        ss[nums].r = x2;

        ss[nums].h = y1;

        ss[nums].f = ;

        //记录上边

        ss[nums+].l = x1;

        ss[nums+].r = x2;

        ss[nums+].h = y2;

        ss[nums+].f = -;

        //记录横坐标

        pos[nums] = x1;

        pos[nums+] = x2;

        nums+=;

      }

      sort(ss,ss+nums,cmp);

      sort(pos,pos+nums);

      int m = ;

      for (int i=;i<nums;i++)//离散去重

        if (pos[i]!=pos[i-])

          pos[m++]=pos[i];

      memset(tree,,sizeof(tree));

      build(,,m-);//离散区间就是[0,m-1]

//      for (int i=0;i<=m*4+2;i++){

//        cout<<tree[i].l<<"-"<<tree[i].r<<endl;

//      }

      double ans = ;

      for (int i=;i<nums-;i++)

      {

          int l = binary(ss[i].l,,m-);//二分找到s[i].l对应的离散化后的值

          int r = binary(ss[i].r,,m-)-;//二分找到右端点但是由于需要把点转区间，因此减一

//          cout<<ss[i].l<<"->"<<l<<" ";

//          cout<<ss[i].r<<"->"<<r<<" ";

//          cout<<ss[i+1].h<<"-"<<ss[i].h<<endl;

          update(,l,r,ss[i].f);//更新区间

          ans+=(ss[i+].h-ss[i].h)*tree[].len;

      }

        printf("Test case #%d\n", ++Case);

        printf("Total explored area: %.2f\n\n", ans);

  }

  return ;

}

相关文章