Gooooooal

记得是去年的12月份，在HDU上开始了各大OJ的切题。一开始所到之处就是A+B。然后很认真的以为HDU的OJ是按难度来编排题号的，所以也就认真的从1000做下去了。没做多少题就发现难度很大，对于一个刚学会语言的控制结构的初学者来说，没有强大的抽象思维能力，很难顺切。然后就是开始了各种搜书活动。从《The C Programming Language》、《C Primer Plus》、《C++ Primer》到《Introduction to Algorithm》、《Data Structures》、《Thinking in C++》，短短半个月，败掉了好多金，不过我个人更倾向于“投资”这种说法。眼看大半年过去了，C++的面向对象技术依然一知半解，几本书同时推进的确压力很大，特别是《Introduction to Algorithm》，没有OI功底的我看着就如天书一般，唯一值得庆幸的是我还在坚持，也陆续完结了一些书本的学习。不过很多书籍还是要多多回顾和联系。

最近的集训最大的感触还是弱校的ACM环境确实不好，有人游戏有人看片，专题准备的好坏也就不予评价，但是至少我们既然选择做了，就要好好准备。想想我花了1个月去攻克八数码，仅仅是想让我们都少走弯路，暑期回家的那20天，切了ZJU和HDU大部分的search，也就是为了呈现给队友们更好的专题。但是我很失望，队列是什么居然还要我花半个小时去解释，状态压缩过程中的位操作还要我在黑板演示，什么hash也都不知道。我本来打算讲解如何去分析search以及search中的细节的运用，却演变成了基础课一般。更夸张的是，几天下来，很多东西主讲人都更在乎的是如何将题目转化到模板，很少去关注这个算法是如何产生的。也就好比高中有些科目，老师只叫我们如何解题，告诉我们记住就好，却不告诉我们为何这么解。很多人大概是抱着混日子的想法来集训的吧，居然还有人准备Big Number，我真想冲上去说一句Big Numer用Java可以瞬秒！Math Theory这一讲居然讲素数，讲欧几里德，讲中国剩余定理。好吧，你讲就讲吧，里面的定理居然不给我证明，真是扯淡啊！有人会说我们才大一，但是怎么不想想几天后我们就是大二的人了。不过有几个人的专题也着实让我喜欢，胡bw的几何，lkj的DP都让我感受颇深。bw的几何带给我的不仅仅局限于几何，而且深入了离散化操作以及线段树的操作，的确让我很惊喜。

贴一个代码，也算是这几天来最有成就感的事情，倘若不是bw的讲解，或许我至今都不知道这就是离散化操作。

/*
这段程序的效率不是很高，不过容易理解
它的主要原理是，把 Y 轴离散化（以所有矩形的Y轴坐标为间断点）
把线段放进线段树中，记录纵线，按X轴排序，（最后会沿X轴正方向把面积一层一层地加起来 ）
用cover记录线段被矩形覆盖的次数，当然被覆盖两次以上的就符合条件了
然后用crossLen记录在该横坐标，对应的纵坐标上有多少长度被覆盖两次（这里就用到线段树了）
然后乘上离下个坐标的距离，就得到了该层的面积；最后把每层的加起来就是答案。
*/
#include<stdio.h>
double y[5000];
struct TREE
{
    double left,right,len,crossLen;
    struct TREE *leftSon,*rightSon;
    int cover;
}tree[5000],*Root;

struct line
{
    double x,y1,y2;
    int cover;
}point[5000],Temp;//用于记录纵行

int idx; //用于树的生长

struct TREE *CreatKid()
{
    struct TREE *p;
    p=&tree[idx++];
    p->cover=0;
    p->len=p->crossLen=0;
    p->leftSon=NULL;
    p->rightSon=NULL;
    return p;
}//为root找一个tree里的空间，并初始化

struct TREE *CreatTree(int left,int right)
{
    struct TREE *root=CreatKid();
    root->left=y[left];
    root->right=y[right];
    if(right-left>1)//直到两个值在数组中相邻
  	{
       int mid=(left+right)>>1;
       root->leftSon=CreatTree(left,mid);
       root->rightSon=CreatTree(mid,right);
    }
    return root;
}

void GetLen(struct TREE*root)
{
    root->len=0;//len表示覆盖长度
    if(root->cover>0)
        root->len=root->right-root->left;
    else if(root->leftSon!=NULL)
        root->len=root->leftSon->len+root->rightSon->len;
}

//crossLen记录被覆盖两次以上的纵向长度
void GetCrossLen(struct TREE *root)
{
    root->crossLen=0;
    if(root->cover>1)
        root->crossLen=root->right-root->left;
    else if(root->leftSon!=NULL)
    {
        if(root->cover==1)
            root->crossLen=root->leftSon->len+root->rightSon->len;
        else
            root->crossLen=root->leftSon->crossLen+root->rightSon->crossLen;
    }
}

//需要注意的是,cover进入这个程序后就不可能小于零
void UpdateLen(struct TREE*root)
{
    GetLen(root);
    GetCrossLen(root);
}

//更新操作，程序的主要部分，是个递归函数，汇集子孙们更新后的数据给头
void Update(struct TREE*root,struct line t)
{
    if(root->left==t.y1&&root->right==t.y2)
    {
        root->cover+=t.cover;
        UpdateLen(root);
        return;
    }
    if(t.y1>=root->leftSon->right)
        Update(root->rightSon,t);
    else if(t.y2<=root->rightSon->left)
        Update(root->leftSon,t);
    else
    {
        struct line tmp=t;
        tmp.y2=root->leftSon->right;
        Update(root->leftSon,tmp);
        tmp=t;
        tmp.y1=root->rightSon->left;
        Update(root->rightSon,tmp);
    }
    UpdateLen(root);
}

int main()
{
    int N,cas,i,j,u,k;
    double x1,x2,y1,y2,ans,temp;
    scanf("%d",&cas);
    while(cas--)
 	{
        scanf("%d",&N);
        idx=j=0;
        ans=0;//用来记录最后的面积
        for(i=0;i<N;i++,j+=2)
	 	{
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            point[j].x=x1;
            point[j+1].x=x2;
            point[j+1].y1=point[j].y1=y1;
            point[j+1].y2=point[j].y2=y2;
            point[j].cover=1;
            point[j+1].cover=-1;
            y[j]=y1;
            y[j+1]=y2;
	 	}

	 	//对Y进行排序，为纵行离散化做准备，用于创建树
        for(k=0;k<j;k++)
        {
            for(u=k;u<j;u++)
            {
                if(y[k]>y[u])
                {
                    temp=y[k];
                    y[k]=y[u];
                    y[u]=temp;
                }
            }
        }

        //对point按X进行排序 ,就是对纵行进行排序
        for(k=0;k<j;k++)
        {
            for(u=k;u<j;u++)
            {
                if(point[k].x>point[u].x)
                {
                    Temp=point[k];
                    point[k]=point[u];
                    point[u]=Temp;
                }
            }
        }
        Root=CreatTree(0,j-1);//创建了线段树，并带回了树的头
        Update(Root,point[0]);//更新操作
        for(i=1;i<j;i++)
        {
            ans+=Root->crossLen*(point[i].x-point[i-1].x);
            Update(Root,point[i]);
        }
        printf("%.2lf\n",ans);
    }
    return 0;
}