POJ - 1151(线段树+扫描线)

题目：click
题意：给出了矩形的左上角以及右下角的坐标，求所有矩阵构成的图形的面积。
思路：先给出扫描线的定义，图是偷的。。。。

可以看到，实质上给定的n个矩形，平行于y轴的有2 * n个，同理x轴，将线全部延长就分割成了许多的小矩形，可以从一边入手，上图是以平行于x轴去扫描的，确定从上或者从下开始，扫描每次碰到的边需要分为入边或者出边，入边时需要加长度，出边相反就不需要计算这条出边之后的贡献。
那么依然是从上到下平行于x轴去扫描的，垂直于x轴的段我们不知道，要计算矩形的面积就需要，我们知道了高，就需要知道x轴的长段之后相乘即可。线段树就是为了去维护x轴的段，之前说了分割成里2$*$∗n条线，即2$*$∗n-1段，线记录标号，去维护一段的长度。由于线段可能重合，所以处理一下。
可见代码。(代码是平行于y轴从左到右去扫描，线段树维护y轴的段)。这里的线段树是以端点去处理的，注意一下。
思路源于：click

#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<istream>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<queue>
#define inf 0x3f3f3f3f
#define llinf 0x3f3f3f3f3f3f3f3f
#define MAX_len 210*4
using namespace std;
typedef long long ll;
#define m ((l+r)>>1)
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
struct A {
    int l,r;
    double left,right;
    double len;
    int cover;
}tree[MAX_len];
double y[MAX_len];
struct B{
    double x,y1,y2;
    int flag;//入边或者出边
}node[MAX_len];
void build_tree(int p,int l1,int r1)
{
    tree[p].l=l1,tree[p].r=r1;
    tree[p].left=y[l1];
    tree[p].right=y[r1];
    tree[p].len=0;
    tree[p].cover=0;
    if(tree[p].l+1==tree[p].r)
        return ;
    int mid=(l1+r1)/2;
    build_tree(p*2,l1,mid);
    build_tree(p*2+1,mid,r1);
}
void solve(int p)
{
    if(tree[p].cover>0)
    {
        tree[p].len=tree[p].right-tree[p].left;
    }
    else if(tree[p].r-tree[p].l==1)
    {
        tree[p].len=0;
    }
    else
        tree[p].len=tree[p*2].len+tree[p*2+1].len;
}
void update(int p,B temp)
{
    if(temp.y1==tree[p].left&&temp.y2==tree[p].right)
    {
        tree[p].cover+=temp.flag;
    }
    else if(temp.y2<=tree[p*2].right)
    {
        update(p*2,temp);
    }
    else if(temp.y1>=tree[p*2+1].left)
    {
        update(p*2+1,temp);
    }
    else
    {
        B tmp;
        tmp=temp;
        tmp.y2=tree[p*2].right;
        update(p*2,tmp);
        tmp=temp;
        tmp.y1=tree[p*2+1].left;
        update(p*2+1,tmp);
    }
    solve(p);
}
bool cmp(B t1,B t2)
{
    return t1.x<t2.x;
}
int main()
{
    int n;
    int yy=1;
    while(~scanf("%d",&n)&&n)
    {
        int i,j,k;
        int t=1;
        for(i=1;i<=n;i++)
        {
            scanf("%lf %lf",&node[t].x,&y[t]);
            scanf("%lf %lf",&node[t+1].x,&y[t+1]);
            node[t].y1=y[t];
            node[t].y2=y[t+1];
            node[t+1].y1=y[t];
            node[t+1].y2=y[t+1];
            node[t].flag=1;
            node[t+1].flag=-1;
            t+=2;
        }
        sort(node+1,node+t,cmp);
        sort(y+1,t+y);
        build_tree(1,1,t-1);
        update(1,node[1]);
        double ans=0;
        for(i=2;i<t;i++)
        {
            ans+=tree[1].len*(node[i].x-node[i-1].x);
            update(1,node[i]);
        }
        printf("Test case #%d\n",yy++);
        printf("Total explored area: %.2f\n\n",ans);
    }
    return 0;
}