POJ 1151 - Atlantis 线段树+扫描线..

扫描线..可以看成一根平行于x轴的直线..至y=0开始往上扫..直到扫出最后一条平行于x轴的边..但是真正在做的时候..不需要完全模拟这个过程..扫描线的做法是从最下面的边开始扫到最上面的边.

线段树: 本题用于动态维护扫描线在往上走时..x哪些区域是有合法面积的..

几个图说明扫描线扫描..线段树维护的过程..:

初始状态

扫到最下边的线,点更新1~3为1

扫到第二根线,此时将计数器不为0的长度*上线两根线的长度,得到绿色的面积,加到答案中去.随后更新计数

同上,将黄色的面积加到答案中去

同上,将灰色的面积加到答案中去

同上,将紫色的面积加到答案中去

同上,将蓝色的面积加到答案中去

#include
#include
#include
#include
#include 
#include
#include
#include
#define oo 1000000007
#define ll long long
#define pi acos(-1.0)
#define MAXN 405
using namespace std;
struct node
{
      double l,r,y;
      int tp;
      bool operator <(node a) const
      {
            return y1)
      {
            mid=(l+r)>>1;
            if (X[mid]<=x) l=mid;
               else r=mid;
      }
      return l;
}
void update(int x,int c,int l,int r,int now)
{
      if (l==r)
      {
            Times[x]+=c;
            if (Times[x]) sum[now]=X[x+1]-X[x];
            if (!Times[x]) sum[now]=0;
            return;
      }
      int mid=(l+r)/2;
      if (x<=mid) update(x,c,l,mid,now<<1);
      if (mid