哈夫曼树

CodeForces 226 B Naughty Stone Piles

Posted on

遇到的第二道哈夫曼树,这个哈夫曼树有些特别,当你将两个结点组合的时候,你只需要付出权值较小的花费。
简单说,结点权值组合的时候并不会产生新的结点!!
这就可以完全摒弃优先队列,直接用数组实现以求更为高效。

上次意外地发现两个队友都不会哈夫曼树……真是惊了……

题意:
有几堆石头,要你将他们堆成一堆。两堆石头堆成一堆的花费是石头堆较小的石头数量。q个询问,每次询问限制一堆石头,被其他石头合并的次数。

思路:
这道题,若是转化成图来说就是一个k叉哈夫曼树,然而不会产生新结点,也就是说所有结点的权值和位置都已经可以直接求得了。
将他降序排序,每次将同一层的权值乘以他的深度就是该层的花费。

: 下表很容易爆 int 自己想想很容易想到……
然而RE了好几发……

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int maxn = 2e5 + 5;
int n;
ll ans[maxn], sum[maxn], ary[maxn];

void solve(int q)
{
    ll dep = 1, idx = 1, nxt;
    ll tmp, res = 0, d = q;
    while (idx <= n) {
        nxt = idx + d <= n ? idx + d : n;
        tmp = sum[nxt] - sum[idx];
        res += tmp * dep;
        idx += d, dep++, d *= q;
    }
    printf("%lld ", ans[q] = res);
}

int main()
{
    int qn, q;
    scanf("%d", &n);
    range(i, 1, n) scanf("%lld", ary + i);
    sort(ary + 1, ary + 1 + n, greater<int>());
    range(i, 1, n) sum[i] = ary[i] + sum[i - 1];
    scanf("%d", &qn);
    while (qn--) {
        scanf("%d", &q);
        if (ans[q])
            printf("%lld ", ans[q]);
        else
            solve(q);
    }
    return 0;
}
Trie

Trie入门与模板

Posted on

简介

Trie ,又称前缀树或者是字典树,不仅在字符串的应用广泛,在数据结构中也有很多相应的题目,是数据结构中用空间兑换时间的典型。

下面是两个入门题

HDU 1251 统计难题

题意:
给定多个字符串,多个询问,问你以所询问字符串为前缀的字符串数量。

思路:
构造Trie,插入的时候打个顺便再对前缀计数即可。

AC Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000005;
int ch[N][30], val[N], sz;

void insert(char *s) 
{
    int u = 0, len = strlen(s);
    for (int i = 0; i < len; i++) {
        int k = s[i] - 'a';
        if (!ch[u][k]) {
            memset(ch[sz], 0, sizeof(ch[sz]));
            val[sz] = 1;
            ch[u][k] = sz++;
        }
        else
            val[ch[u][k]]++;
        u = ch[u][k];
    }
}

int query(char *s) 
{
    int u = 0, len = strlen(s);
    for (int i = 0; i < len; i++) {
        int k = s[i] - 'a';
        if (!ch[u][k])
            return 0;
        u = ch[u][k];
    }
    return val[u];
}

int main() 
{
    char str[15];
    memset(ch[0], 0, sizeof(ch[0]));
    sz = 1;
    while (gets(str) && strlen(str) != 0)
        insert(str);
    while (scanf("%s", str) == 1)
        printf("%d\n", query(str));
    return 0;
}

HDU 1075 What Are You Talking About

题意:
给定字符串以及映射的字符串,再给定另几个字符串,让你把映射后的写出来。

思路:
大致的思路都是有的,构建Trie,再对每个单词进行查询。
但是!!!有非常非常多的坑!!!我觉得字符串的坑都这么多!!!
但是我写这篇博文实际上是我A题一周后了,具体哪些我也忘了……想知道,就看代码或者discuss吧。
真的是坑哭了…… 交了22发才A……

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
const int maxn = 500010;
const int sigma_size = 27;

struct Trie {
    int ch[maxn][sigma_size];
    char trans[maxn][12];
    bool isEnd[maxn];
    int sz;
    Trie()
    {
        sz = 1;
        memset(ch[0], 0, sizeof ch[0]);
        isEnd[0] = false;
    }
    int getIdx(const char& c) { return c - 'a'; }

    void insert(char* s, char* tar)
    {
        int u = 0, len = strlen(s);
        for (int i = 0; i < len; i++) {
            int idx = getIdx(s[i]);
            if (!ch[u][idx]) {
                memset(ch[sz], 0, sizeof ch[sz]);
                isEnd[sz] = false;
                ch[u][idx] = sz++;
            }
            u = ch[u][idx];
        }
        memcpy(trans[u], tar, sizeof trans[u]);
        isEnd[u] = true;
    }

    void query(char* s)
    {
        int u = 0, len = strlen(s);
        for (int i = 0; i < len; i++) {
            int idx = getIdx(s[i]);
            if (!ch[u][idx]) {
                printf("%s", s);
                return;
            }
            u = ch[u][idx];
        }
        if (isEnd[u])
            printf("%s", trans[u]);
        else
            printf("%s", s);
    }
};

int main()
{
    Trie trie;
    char str[2][15];
    char buf[3005], ch;
    int id=0;
    scanf("%s", str[0]);
    while (scanf("%s", str[0]) && strcmp(str[0], "END") != 0) {
        scanf("%s", str[1]);
        trie.insert(str[1], str[0]);
    }
    scanf("%s", str[0]);
    getchar();
    while (scanf("%c", &ch)) {
        if (isalpha(ch))
            buf[id++] = ch;
        else {
            buf[id] = '\0';
            id = 0;
            if (strcmp(buf, "END") == 0)
                break;
            trie.query(buf);
            putchar(ch);
        }
    }
    return 0;
}

指针模板

query函数针对的是 hdu 1075

struct TrieNode {
    TrieNode* nxt[sigma_size];
    char* trans;
    char ch;
    bool isEnd;
    TrieNode()
    {
        trans = NULL;
        isEnd = false;
        memset(nxt, 0, sizeof ch);
    }
    ~TrieNode()
    {
        delete trans;
    }
};

struct Trie {
    TrieNode* root;
    Trie()
    {
        root = new TrieNode;
    }
    ~Trie()
    {
        freeTree(root);
    }
    int getIdx(const char& c) { return c - 'a'; }

    void insert(char* s, char* tar)
    {
        int len = strlen(s), idx;
        TrieNode *cur = root, *tmp;
        for (int i = 0; i < len; i++) {
            idx = getIdx(s[i]);
            if (cur->nxt[idx] == NULL) {
                tmp = new TrieNode;
                tmp->ch = s[i];
                cur->nxt[idx] = tmp;
            }
            cur = cur->nxt[idx];
        }
        cur->isEnd=true;
        cur->trans = new char[strlen(tar) + 2];
        memcpy((cur->trans), tar, strlen(tar) + 1);
    }

    void query(char* s)
    {
        int len = strlen(s), idx;
        TrieNode* cur = root;
        for (int i = 0; i < len; i++) {
            idx = getIdx(s[i]);
            if (cur->nxt[idx] == NULL) {
                printf("%s", s);
                return;
            }
            cur = cur->nxt[idx];
        }
        if (cur->isEnd)
            printf("%s", cur->trans);
        else
            printf("%s", s);
    }

    void freeTree(TrieNode* cur)
    {
        for (int i = 0; i < sigma_size; i++)
            if (cur->nxt[i])
                freeTree(cur->nxt[i]);
        delete cur;
    }
};

数组模板

query函数针对的是 hdu 1075

struct Trie {
    int ch[maxn][sigma_size];
    char trans[maxn][12];
    bool isEnd[maxn];
    int sz;
    Trie()
    {
        sz = 1;
        memset(ch[0], 0, sizeof ch[0]);
        isEnd[0] = false;
    }
    int getIdx(const char& c) { return c - 'a'; }

    void insert(char* s, char* tar)
    {
        int u = 0, len = strlen(s);
        for (int i = 0; i < len; i++) {
            int idx = getIdx(s[i]);
            if (!ch[u][idx]) {
                memset(ch[sz], 0, sizeof ch[sz]);
                isEnd[sz] = false;
                ch[u][idx] = sz++;
            }
            u = ch[u][idx];
        }
        memcpy(trans[u], tar, sizeof trans[u]);
        isEnd[u] = true;
    }

    void query(char* s)
    {
        int u = 0, len = strlen(s);
        for (int i = 0; i < len; i++) {
            int idx = getIdx(s[i]);
            if (!ch[u][idx]) {
                printf("%s", s);
                return;
            }
            u = ch[u][idx];
        }
        if (isEnd[u])
            printf("%s", trans[u]);
        else
            printf("%s", s);
    }
};
二叉查找树

关于传参的两种方式 传值与传址 的深入理解 (附 hdu3999

Posted on

真的真的真的真的好久没码了………………

最近因为要复习数据结构所以才兴起想要码一些跟考试相关的

于是找了一下 BST 和 AVL 的题做做 结果一下搜就找到了 hdu3999

解法很简单 只要建立一个 BST 再对其先序遍历即可
然而…………

问题出在这个代码上

int main()
{
    int tmp;
    while(scanf("%d",&n)!=EOF)
    {
        root=NULL;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&tmp);
            InsertNode(root,tmp);
            if(root==NULL)
                cout<<1111<<endl;
        }
        FirstOrderSearch(root);
        puts("");
    }
    return 0;
}

插入函数如下

void InsertNode(node* now,int value)
{
    if(now==NULL)
    {
        now = new node;
        now -> value = value;
        return ;
    }
    else if(value < now -> value)
        InsertNode(now->left,value);
    else if(value > now -> value)
        InsertNode(now -> right, value);
}

咋看下真的没什么问题 然而实际上还是会输出n个 1111
这就说明 root 它一直都没有变化

“纳尼不是只要传地址 , 那么这个变量就一定会随之改变的不是么。。。”

想了一下才想通 传参在本质上来说完全只有一种方法 就是传值

传址传址 也只是把指针这个变量的值 给传了过去 而如果我们对这个地址取值那么自然而然的就可以改变这个变量的值

以这里的代码为例 我在主函数中的 root变量初始化为 NULL 传给 InsertNode 变量now拥有了 NULL 但是在这里now的所有变化将根本不会影响到main中的root

换言之 对于指针的传参 只有 *指针(指针所指的值)才会能在全局变化

所以如果要继续我以上的写法 解法有二:

  1. 只要将这个root 这个指针的地址传给函数处理即可
  2. 当然 我也可以在最开始的时候就先把根节点给定义了 再对根节点传参也可

综上

传参在本质上只有将实参的值传给形参 而所谓的传址 我们只能理解成一个小技巧 否则会带来很多习惯性误导

AC Code

法 1 :(因为第一次这么写 运算符的等级忘了 所以保险点就都加了括号…………)

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
int n;

struct node
{
    int value;
    node *left;
    node *right;
    node():left(NULL),right(NULL) {}
};

void InsertNode(node** now,int value)
{
    if(*now==NULL)
    {
        *now=new node;
        (*now)->value=value;
        return ;
    }
    if(value < (*now) -> value)
        InsertNode(&((*now)->left),value);
    else if(value > (*now) -> value)
        InsertNode(&((*now) -> right), value);
}

void FirstOrderSearch(node* now,node* root)
{
    if(now==root)
        printf("%d",now->value);
    else printf(" %d",now->value);
    if(now->left)
        FirstOrderSearch(now->left,root);
    if(now->right)
        FirstOrderSearch(now->right,root);
    delete now;
}

int main()
{
    int tmp;
    while(scanf("%d",&n)!=EOF)
    {
        node* root=NULL;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&tmp);
            InsertNode(&root,tmp);
        }
        FirstOrderSearch(root,root);
        puts("");
    }
    return 0;
}
哈夫曼树

哈夫曼编码

Posted on

传送门

OJ小作业 很久以前第一次听说哈夫曼树问了一下煞笔室友 听他很不屑地说 只是一个贪心而已 我也就没怎么在意

最近李总上课点名不得不去上一下 可惜也只是到那里发了一下呆 点了一下到就过去了 他在讲哈夫曼编码的时候我也没去听

搞得我刚开始看到这题的时候有点小蒙蔽 还好数据比较水 不然估计要卡很长时间 (因为完全是我根据以前的知识xjb搞的 还好还好是一A

下面是源码+注解 (因为完全是自己看了远离后搞得 可能有点烦........

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>

#define root tree[id]
#define leson tree[ldir]
#define rison tree[rdir]

using namespace std;
const int maxn = 104;
int len, all_time;
int tree_root;//根节点
char to_c[maxn];//由节点的值转化为字符
char tar[maxn * 100];
char tar_ch;//当前目标字符
char output[maxn];//输出数组
bool flag;//标记  如果已经输出就直接返回

struct node {
    int lson, rson;
    int tim;//结点生成时间  所有原结点初始化为0
    int order;//节点编号
    int val;//结点的值
    bool operator<(const node& a) const
    {
        if (val != a.val)
            return val > a.val;
        if (tim != a.tim)
            return tim > a.tim;
        return order > a.order;
    }//按照题意出队
};

priority_queue<node> que;
node tree[maxn << 2];

int CreatTree()
{
    node ta, tb;
    int id;
    while (que.size() > 1) {
        ta = que.top();
        que.pop();
        tb = que.top();
        que.pop();
        id = len + all_time;
        root.lson = ta.order;
        root.rson = tb.order;
        root.val = ta.val + tb.val;
        root.order = id;
        root.tim = all_time++;
        que.push(root);
        // printf("%d %d\n",ta.order,tb.order);
    }//取出两个节点并合并再入队   最后剩余的便是根节点
    ta = que.top();
    que.pop();
    return ta.order;
}

void lock(int id, int dep)
{
    if (flag)//若已经输出过了   就直接返回
        return;
    int ldir = root.lson, rdir = root.rson;
    if (ldir) {
        output[dep] = '0';
        lock(ldir, dep + 1);
    }
    if (rdir) {
        output[dep] = '1';
        lock(rdir, dep + 1);
    }
    if (!ldir && !rdir && to_c[root.order] == tar_ch) {  //确保该结点为叶子结点也可以省点时间
        for (int i = 0; i < dep; i++)
            putchar(output[i]);
        flag = true;//标记为true
    }
}

int unlock(int index)
{
    int id = tree_root;
    while (root.lson || root.rson) {
        if (tar[index] == '0')  // 0 向左 1向右
            id = root.lson;
        else
            id = root.rson;
        index++;
    }
    putchar(to_c[root.order]);
    return index;//返回转化后的index
}

int main()
{
    while (scanf("%s", to_c + 1) != EOF) {
        len = strlen(to_c + 1);
        for (int id = 1; id <= len; id++) {
            scanf("%d", &root.val);
            root.order = id;
            root.tim = 0;
            root.lson = root.rson = 0;
            que.push(root);
        }
        all_time = 1;
        tree_root = CreatTree();
        // printf("root: %d\n",tree_root);
        // for(int id=1;id<=tree_root;id++)
        //    printf("order: %d  val: %d  lson: %d  rson:%d\n",root.order,root.val,root.lson,root.rson); //可取消注释查看建树是否正确
        scanf("%s", tar);
        int tar_len = strlen(tar);
        for (int i = 0; i < tar_len; i++) {
            tar_ch = tar[i];
            flag = false;
            lock(tree_root, 0);
        }
        puts("");
        scanf("%s", tar);
        tar_len = strlen(tar);
        int i = 0;
        while (i < tar_len)
            i = unlock(i);
        puts("");
    }
    return 0;
}
线段树

HDU 3275 Light

Posted on

题意很简单 给你一串长度为n只有0,1的字符串,每次操作固定操作m长度的子串 问至少多少次才能使字符串全为 1

一开始没啥思路 后来发现每次找到第一个 0 的位置再以他为起点进行更新,重复操作要么全为 1 要么无法更新(别问我为什么,这是我队友跟我说的,我负责码线段树

这题我觉得有两个坑点

1.当m==0 的时候 这还能玩??一个字符都不让动 出题的人也是脑残,,,总是动一些小条件 总之这时候就输出他的其实状态 ,即如果全为 1 输出0 否则 输出-1

2.延迟更新的时候,这个就需要对线段树有一定的理解了 因为是延迟更新,在还未更新的时候可能存在对某一个区间多次标记 标记奇数次次就是0,1反转,偶数次就是不变咯 这里我对lazy标记进行异或,一切迎刃而解

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define root tree[id]
#define lson tree[id<<1]
#define rson tree[id<<1|1]

using namespace std;
const int maxn=100005;
int st,en;
struct segtree
{
    int le,ri;
    int sum,len,d;
} tree[maxn*4];
char ch[maxn];

void pushdown(int id)
{
    if(root.d&&root.le!=root.ri)
    {
        lson.sum=lson.len-lson.sum;
        rson.sum=rson.len-rson.sum;
        lson.d^=1;
        rson.d^=1;
        root.d=0;
    }
}

void build_tree(int id,int le,int ri)
{
    root.le=le,root.ri=ri,root.len=ri-le+1,root.d=0;
    if(le==ri)
    {
        root.sum=ch[le]-'0';
        return ;
    }
    int mid=(le+ri)>>1;
    build_tree(id<<1,le,mid);
    build_tree(id<<1|1,mid+1,ri);
    root.sum=lson.sum+rson.sum;
}

int query(int id,int le,int ri)
{
    int ans;
    if(root.len==root.sum) return 0;
    if(le==ri) return le;
    pushdown(id);
    int mid=(le+ri)>>1;
    if(ans=query(id<<1,le,mid)) return ans;
    if(ans=query(id<<1|1,mid+1,ri)) return ans;
    root.sum=lson.sum+rson.sum;
    return 0;
}

void update(int id,int le,int ri)
{
    if(st<=le&&ri<=en)
    {
        root.sum=root.len-root.sum;
        root.d^=1;
        return ;
    }
    pushdown(id);
    int mid=(le+ri)>>1;
    if(st<=mid) update(id<<1,le,mid);
    if(en>mid) update(id<<1|1,mid+1,ri);
    root.sum=lson.sum+rson.sum;
}

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(m==0&&n==0) break;
        getchar();
        scanf("%s",ch+1);
        build_tree(1,1,n);
        if(m==0)
        {
            if(tree[1].sum==tree[1].len) printf("0\n");
            else printf("-1\n");
            continue;
        }
        bool flag=true;
        int step=0;
        while(st=query(1,1,n))
        {
            en=st+m-1;
            if(en>n)
            {
                flag=false;
                break;
            }
            step++;
            update(1,1,n);
        }
        if(flag) printf("%d\n",step);
        else printf("-1\n");
    }
    return 0;
}
线段树

HDU 1828 Picture

Posted on

扫描线第二题

求周长

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=20010;
int sum[maxn<<2],segnum[maxn<<2],flag[maxn<<2];//sum与上面一样   segnum记录未被覆盖的竖边数量   flag 同上
bool lseg[maxn<<2],rseg[maxn<<2];////表示某个区间最左边和最右边是否有下底边多于上底边
struct node
{
    int lx,rx;
    int y,d;
    node(){}
    node(int _lx,int _rx,int _y,int _d)
    {
        lx=_lx,rx=_rx,y=_y,d=_d;
    }
    bool operator <(const node& a)const
    {
        if(y==a.y) return d>a.d;
        return y<a.y;
    }
}lines[maxn];

void pushup(int id,int le,int ri)
{
    if(flag[id])
    {
        sum[id]=ri-le+1;
        lseg[id]=rseg[id]=true;
        segnum[id]=2;
    }
    else if(le==ri) sum[id]=lseg[id]=rseg[id]=segnum[id]=0;
    else
    {
        sum[id]=sum[id<<1]+sum[id<<1|1];
        segnum[id]=segnum[id<<1]+segnum[id<<1|1];
        lseg[id]=lseg[id<<1];
        rseg[id]=rseg[id<<1|1];
        if(rseg[id<<1]&&lseg[id<<1|1]) segnum[id]-=2;//矩形相交
    }
}

void update(int id,int le,int ri,int st,int en,int add)
{
    if(st<=le&&ri<=en)
    {
        flag[id]+=add;
        pushup(id,le,ri);
        return ;
    }
    int mid=(le+ri)>>1;
    if(st<=mid) update(id<<1,le,mid,st,en,add);
    if(en>mid) update(id<<1|1,mid+1,ri,st,en,add);
    pushup(id,le,ri);
}

int main()
{
    int n,x1,y1,x2,y2;
    while(scanf("%d",&n)!=EOF)
    {
        int ss=inf,ee=-inf;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            lines[2*i+1]=node(x1,x2,y1,1);
            lines[2*i+2]=node(x1,x2,y2,-1);
            ss=min(x1,ss),ee=max(x2,ee);
        }
        n*=2;
        sort(lines+1,lines+1+n);
        int ans=0,last=0;
        for(int i=1;i<=n;i++)
        {
            update(1,ss,ee,lines[i].lx,lines[i].rx-1,lines[i].d);
            ans+=segnum[1]*(lines[i+1].y-lines[i].y);
            ans+=abs(sum[1]-last);//底边增加的长度
            last=sum[1];
        }
        printf("%d\n",ans);
    }
    return 0;
}
线段树

HDU 1542 Atlantis

Posted on

线段树扫描线入门题

扫描线扫描线 一开始看的时候真的是看的我整个人都不好了 全程懵逼状态 自信心严重受损 最后休整了一天再来看它 用纸和笔动手比划了一点时间才终于算是稍微明白了一点 所以我的建议还是大家自己动手比划一下 毕竟实践出真知 网上的那些题解虽然有图 但他们的语言也只有他们自己读得懂 自己动过手之后才知道他整个过程都是这么精妙

据我所知 线段树的扫描线一般只有两个用处 一个是求覆盖的矩形面积 和覆盖的矩形周长

(毕竟我是鶸 还没碰到过其他用法的扫描线

这题 求面积 数据大 需要离散化

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int maxn=4100;
const double eps=1e-6;
int n,len,flag[maxn];
double ans,xx[maxn],sum[maxn];//xx用于离散化     sum记录扫描线边长   并聚合在sum[1]上
struct line
{
    double lx,rx;
    double y;
    int d;
    line(){}
    line(double _lx,double _rx,double _y,int _d)
    {
        lx=_lx,rx=_rx,y=_y,d=_d;
    }
    bool operator <(const line& a) const
    {
        return y<a.y;
    }
}lines[maxn];

int fin(double a)
{
    int l=1,r=len,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(xx[mid]==a) return mid;
        else if(xx[mid]>a) r=mid-1;
        else l=mid+1;
    }
    return l;
}

void pushup(int id,int le,int ri)//这是最难理解的一步    我就是卡在了这里   之后比划过才知道玄妙
{
    if(flag[id]) sum[id]=xx[ri+1]-xx[le];
    else if(le==ri) sum[id]=0;
    else sum[id]=sum[id<<1]+sum[id<<1|1];
}

void update(int id,int le,int ri,int st,int en,int add)
{
    if(st<=le&&ri<=en)
    {
        flag[id]+=add;
        pushup(id,le,ri);
        return ;
    }
    int mid=(le+ri)>>1;
    if(st<=mid) update(id<<1,le,mid,st,en,add);
    if(en>mid) update(id<<1|1,mid+1,ri,st,en,add);
    pushup(id,le,ri);
}

int main()
{
    double x1,y1,x2,y2;
    int time=0;
    while(scanf("%d",&n),n)
    {
        memset(flag,0,sizeof flag);
        memset(sum,0,sizeof sum);
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            xx[2*i+1]=x1,xx[2*i+2]=x2;
            lines[2*i+1]=line(x1,x2,y1,1);
            lines[2*i+2]=line(x1,x2,y2,-1);
        }
        n*=2,len=1,ans=0;
        sort(xx+1,xx+1+n);
        sort(lines+1,lines+1+n);
        for(int i=2;i<=n;i++) if(xx[i]!=xx[i+1]) xx[++len]=xx[i];//去重
        for(int i=1;i<n;i++)
        {
            int l=fin(lines[i].lx);
            int r=fin(lines[i].rx)-1;
            update(1,1,len,l,r,lines[i].d);
            ans+=sum[1]*(lines[i+1].y-lines[i].y);
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n",++time,ans);
    }
    return 0;
}