一、题目
二、思考
采用红黑树作为基础数据结构，扩展为14.3中的区间树。
第一步：
对每个矩形的左边x和右边x排序，排序结果放在一个序列中。并记录每个x值属于哪个矩形。
如三个矩形的x区间（左边x，右边x）分别是（1，3），（2，4），（3，5），排序结果（x值，属于哪个矩形）是（1，1），（2，2），（3，1），（3，3），（4，2），（5，3）。
第二步：
依次处理排序结果（x，i）。
（1）如果x是矩形i的左边x，则求出区间树中与矩形i的y区间相交的区间个数，再把矩形i的y区间插入到区间树中。
（2）如果x是矩形i的右边x，则将矩形i的y区间从区间树中删除
三、代码
- #include <iostream>
- #include <algorithm>
- using namespace std;
- #define BLACK 0
- #define RED 1
- #define N 10//矩形的个数
- //区间结构
- struct interval
- {
- int low;
- int high;
- interval(){};
- interval(int l, int h):low(l), high(h){}
- bool operator==(interval &b)
- {
- if(low == b.low && high == b.high)
- return 1;
- return 0;
- }
- };
- //矩形结构
- struct Rectangle
- {
- interval x;
- interval y;
- };
- //用于排序
- struct Sort_Node
- {
- int x;
- int id;//x所属的矩形的编号
- Sort_Node(){}
- Sort_Node(int a, int b):x(a),id(b){}
- };
- //用于排序
- bool cmp(Sort_Node a, Sort_Node b)
- {