POJ 1151 - Atlantis 線段樹+掃描線..

 離散化: 將所有的x軸坐標存在一個數組裡..排序.當進入一條線段時..通過二分的方式確定其左右點對應的離散值...

   掃描線..可以看成一根平行於x軸的直線..至y=0開始往上掃..直到掃出最後一條平行於x軸的邊..但是真正在做的時候..不需要完全模擬這個過程..掃描線的做法是從最下面的邊開始掃到最上面的邊.

   線段樹: 本題用於動態維護掃描線在往上走時..x哪些區域是有合法面積的..

   幾個圖說明掃描線掃描..線段樹維護的過程..:

初始狀態

掃到最下邊的線,點更新1~3為1

掃到第二根線,此時將計數器不為0的長度*上線兩根線的長度,得到綠色的面積,加到答案中去.隨後更新計數

同上,將黃色的面積加到答案中去

同上,將灰色的面積加到答案中去

同上,將紫色的面積加到答案中去

同上,將藍色的面積加到答案中去

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<set>
#include <ctime>
#include<queue>
#include<algorithm>
#include<cmath>
#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 y<a.y;
      }
}line[MAXN<<2];
int n,Times[MAXN<<2];
double X[MAXN<<2],sum[MAXN];
int b_search(double x)
{
      int l,r,mid;
      l=0,r=n+1;
      while (r-l>1)
      {
            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<x)  update(x,c,mid+1,r,(now<<1)|1);
      sum[now]=sum[now<<1]+sum[(now<<1)|1];
      return;
}
int main()
{ 
      int i,j,num,T=0;
      double ans=0; 
      while (~scanf("%d",&n) && n)
      {
            num=0;
            for (i=1;i<=n;i++)
            {
                   double x1,y1,x2,y2;
                   scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
                   line[i*2-1].y=y1,line[i*2-1].l=x1,line[i*2-1].r=x2,line[i*2-1].tp=1;
                   line[i*2].y=y2,line[i*2].l=x1,line[i*2].r=x2,line[i*2].tp=-1;
                   X[++num]=x1,X[++num]=x2;
            }
            n=n*2;
            sort(X+1,X+1+num);
            sort(line+1,line+1+n);
            memset(sum,0,sizeof(sum));
            memset(Times,0,sizeof(Times));
            ans=0;
            for (i=1;i<=n;i++)
            {
                   ans+=sum[1]*(line[i].y-line[i-1].y); 
                   int l,r;
                   l=b_search(line[i].l);
                   r=b_search(line[i].r)-1;
                   for (j=l;j<=r;j++) update(j,line[i].tp,1,n-1,1);
            }
            printf("Test case #%d\nTotal explored area: %.2f\n\n",++T,ans);
      }
      return 0;
}