一，问题：
1. 给定一个源区间[x,y]和N个无序的目标区间[x1,y1] [x2,y2] ... [xn,yn]，判断源区间[x,y]是不是在目标区间内。
2. 给定一个窗口区域和系统界面上的N个窗口，判断这个窗口区域是否被已有的窗口覆盖。
二，解法：
问题一：
先用区间的左边界值对目标区间进行排序O(nlogn)，对排好序的区间进行合并O(n)，对每次待查找的源区间，用二分查出其左右两边界点分别处于合并后的哪个源区间中O(logn)，若属于同一个源区间则说明其在目标区间中，否则就说明不在。
#include <iostream>
#include <algorithm>
using namespace std;
struct Line
{
int low, high;
bool operator<(const Line &l) const
{return low<l.low;}
};
#define MAXN 10001
Line lines[MAXN]; // 目标区间
int ncnt = 0; // 合并后区间的个数
#define N 101
Line sl[N]; // 待查询的源区间
// 用二分查找找出key所在的区间，以区间的low作为划分
int GetIndex(int key)
{
int u, v;
u = 0; v = ncnt-1;
while (u<=v) // u,v可取等号
{
int m = (u+v)>>1;
if (key >= lines[m].low)
u = m+1;
else
v = m-1;
}
return v;
}
int main()
{
int n, k, i, j;
cin >> n >> k; // n是目标区间的个数,k是待查询的源区间的个数
for (i=0; i<n; i++)
cin >> lines[i].low >> lines[i].high;
for (i=0; i<k; i++)
cin >> sl[i].low >> sl[i].high;
// 排序O(nlogn)
sort(lines, lines+n);
// 合并O(n)
int lasthigh = lines[0].high;
for (i=1; i<n; i++)
if (lasthigh >= lines[i].low)
lasthigh = lines[i].high;
else
{
lines[ncnt++].high = lasthigh;
lines[ncnt].low = lines[i].low;
lasthigh = lines[i].high;
}
lines[ncnt++].high = lasthigh;
for (i=0; i<k; i++)
{
// 单词查找时间O(logn)
int s1 = GetIndex(sl[i].low);
int s2 = GetIndex(sl[i].high);
if (s1==s2 && sl[i].high <= lines[s2].high)
printf("Yes\n");
else
printf("No\n");
}
}
法二：使用并查集，对每个区间合并到一个子树上，最后判断源区间的x和y的根是否相同。
#include<iostream>
using namespace std;
const int size = 100;
int father[size];
int rank[size];
void make_set(int n)
{
for(int i = 1; i <= n; i ++){
father[i] = i;
rank[i] = 1;
}
}
int find_set(int x)//寻找代表元素
{
if(x != father[x]){ //元素不是单独的段，在某个区间内，返回某个区间代表
father[x] = find_set(father[x]);
}
return father[x];
}
void Union(int x, int y)
{
x = find_set(x);
y = find_set(y);
if(x == y){ //两个在同一个区间
return ;
}
if(rank[x] < rank[y]){
father[x] = y;
}
else{
father[y] = x;
if(rank[x] == rank[y]){
rank[x] ++;
}
}
}
int main()
{
int x1, y1;
cin >> x1 >> y1;//输入要判断区间
int x, y;
int n;
cin >> n; //区间的个数
make_set(size);
while(n --){
cin >> x >> y; //输入每个区间
if(x > y){//这一步很关键，表示考虑的周到
swap(x, y);
}
for(int i = x + 1; i <= y; i++){//将区间内的 段合并到已有区间
Union(x, i);
}
}
if(find_set(x1) == find_set(y1)){
cout << "yes" << endl;
}
else{
cout << "no" << endl;
}
system("pause");
}
（1,3）结合后 father[1-3]=1 rank[1]=2;其余为1
（2,4）结合后 fahter[1-4]=1 rank[1]=2 ;其余为1
说明：（1，4）为整个区间，代表为1
法三：将无序的目标区间排序后，再合并成几个有序的区间，然后把源区间和有序的目标区间比较。
#include<iostream>
#include<vector>
using namespace std;
typedef pair<int, int> section;
bool cmp(section a, section b)
{
return a.first < b.first;
}
int main()
{
section src, tmp;
cin >> src.first >> src.second; //要查找的
vector<section> v;
while(cin >> tmp.first >> tmp.second, tmp.first | tmp.second){
v.push_back(tmp);
}
sort(v.begin(), v.end(), cmp);//按第一个域，从小到大排序
vector<section> res;
vector<section>::iterator it = v.begin();
int begin = it->first;//记录区间的开始部分
int end = it->second;//记录区间的开始部分
if((it+1)==v.end()) //如果只有一个区间
res.push_back(make_pair(begin, end));
else
{
it ++;
for(; it != v.end(); it++){
if(end <= it->first){ //如果第一个pair 的第二个元素，小于下一个pair 的第一个元素。
res.push_back(make_pair(begin, end)); //插入第一个区间
begin = it->first;
end = it->second;
}
else if( (end > it->first) && (end <=it->second))
{
//res.push_back(make_pair(begin, end); //插入第一个区间
//begin = it->first;
end = it ->second;
if((it+1)==v.end())
res.push_back(make_pair(begin, end));
}
}
}
bool solve = false;
it = res.begin();
for(; it != res.end(); it ++){
if(src.first >= it->first && src.second <= it->second){
solve = true;
break;
}
}
if(solve){
cout << "in" << endl;
}
else{
cout << "out" << endl;
}
system("pause");
}
问题二解法：
这个问题适合使用线段树来解答，单次查找的时间复杂度为O(nlogn)，当然也能用数组解答，但单次查找的时间复杂度会增加到O(n^2)。这里我们直接使用线段树来解答。
线段树是一棵二叉树，将数轴划分成一系列的初等区间[I, I+1] (I=1,2,..,N-1)。每个初等区间对应于线段树的一个叶结点。线段树的内部结点对应于形如[ I, J ](J – I > 1)的一般区间。由于线段树给每一个区间都分配了结点，利用线段树可以求区间并后的总长度与区间并后的线段数。先给出测试数据（前4行是系统界面上已有的N个窗口，之后的一行是待测试的窗口区域），后面是代码：
4
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
// 线段树的结点
struct SegNode
{
int low, high; // 线段的两端点索引
int ncover; // 线段被覆盖的次数
SegNode *left; // 结点的左子树
SegNode *right; // 结点的右子树
SegNode() {low=high=0;ncover=0;
left=right=NULL;}
};
// 构造线段树，它是一个完全二叉树
void BuildSegTree(SegNode *&tree, int *index, int low, int high)
{
if (low < high)
{
tree = new SegNode;
tree->low = low;
tree->high = high;
if (high-low>1)
{
int m = (low+high)/2;
BuildSegTree(tree->left, index, low, m);
BuildSegTree(tree->right, index, m, high);
}
}
}
// 往线段树中插入线段，即用线段(low,high)来覆盖线段树
void InsertSegTree(SegNode *tree, int low, int high)
{
// 先序遍历
if (low<=tree->low && tree->high<=high)
tree->ncover++;
else if (tree->high-tree->low > 1)
{
int m = (tree->low+tree->high)/2;
if (low < m) InsertSegTree(tree->left, low, high);
if (m < high) InsertSegTree(tree->right, low, high);
}
}
// 从线段树中删除线段
void DeleteSegTree(SegNode *tree, int low, int high)
{
if (low<=tree->low && tree->high<=high)
tree->ncover--;
else if (tree->high-tree->low > 1)
{
int m = (tree->low+tree->high)/2;
if (low < m) DeleteSegTree(tree->left, low, high);
if (m < high) DeleteSegTree(tree->right, low, high);
}
}
// 线段树中是否包含线段(low,high)
bool FindSegTree(SegNode *tree, int low, int high)
{
// 若当前区间被覆盖，且线段(low,high)属于当前区间则返回覆盖
if (tree->ncover && tree->low <= low && high <= tree->high )
return true;
// 若(low,high)没被当前区间覆盖，则将其分为两段，
// 分别考虑是否被子结点表示的区间覆盖
else if (tree->high - tree->low > 1)
{
int m = (tree->low + tree->high) >> 1;
bool ret = true;
if (low<m) ret = FindSegTree(tree->left, low, high<m?high:m);
if (!ret) return false;
if (m<high) ret = FindSegTree(tree->right, m<low?low:m, high);
if (!ret) return false;
return true;
}
return false;
}
#define LEFT true
#define RIGHT false
#define INF 10000
// 表示竖直方向的线段
struct Line
{
int starty, endy; // 竖线的长度
int x; // 竖线的位置
bool inout; // 竖线是长方形的左边还是右边
bool operator<(const Line& a) const{ // 依据x坐标进行排序
return x<a.x;
}
};
// 所有竖直方向的线段
Line lines[INF];
// 对横向超元线段进行分组
int index[INF];
int nCnt = 0;
// 获取key的位置
int GetIndex(int key)
{
// 用二分查找查出key在index中的位置
return lower_bound(index,index+nCnt,key)-index;
}
// 获取key的位置或比它小的最大数的位置
int GetLower(int key)
{
size_t pos = lower_bound(index,index+nCnt,key)-index;
if (key == index[pos]) return pos;
else return pos-1;
}
// 获取key的位置或比它大的最小数的位置
int GetUpper(int key)
{
return lower_bound(index,index+nCnt,key)-index;
}
int main()
{
int nRec;
cin >> nRec;
int i, j;
int x[2], y[2];
// 读取nRec个窗口的数据
for (i=0; i<nRec; i++)
{
cin >> x[0] >> y[0] >> x[1] >> y[1];
// 记录每个长方形的两条竖直边
lines[2*i].x=x[0]; lines[2*i+1].x=x[1];
lines[2*i].starty=lines[2*i+1].starty=min(y[0],y[1]);
lines[2*i].endy=lines[2*i+1].endy=max(y[0],y[1]);
lines[2*i].inout=LEFT; lines[2*i+1].inout=RIGHT;
// 对竖直的线段进行离散化
index[2*i]=y[0]; index[2*i+1]=y[1];
}
// 待查询的窗口区域
Line search[2];
cin >> x[0] >> y[0] >> x[1] >> y[1];
search[0].x=x[0]; search[1].x=x[1];
search[0].starty=search[1].starty=min(y[0],y[1]);
search[0].endy=search[1].endy=max(y[0],y[1]);
search[0].inout=LEFT; search[1].inout=RIGHT;
// 对x坐标进行排序O(nlogn)
sort(index, index+2*nRec);
sort(lines, lines+2*nRec);
// 排除index数组中的重复数据O(n)
for (i=1; i<2*nRec; i++)
if (index[i]!=index[i-1])
index[nCnt++] = index[i-1];
index[nCnt++] = index[2*nRec-1];
// 建立线段树
SegNode *tree;
BuildSegTree(tree, index, 0, nCnt-1);
// 单词查找的时间复杂度为O(nlogn)
bool res;
InsertSegTree(tree, GetIndex(lines[0].starty), GetIndex(lines[0].endy));
for (i=1; i<2*nRec; i++)
{
if (lines[i].inout==LEFT) // 遇窗口的左边界，将其加入线段树
InsertSegTree(tree, GetIndex(lines[i].starty), GetIndex(lines[i].endy));
else // 遇窗口的右边界，将其删出线段树
DeleteSegTree(tree, GetIndex(lines[i].starty), GetIndex(lines[i].endy));
if (lines[i].x!=lines[i-1].x && search[0].x < lines[i+1].x && search[1].x > lines[i].x)
{
// 从待查窗口区域的左边界开始查询直到其右边界结束查询
res = FindSegTree(tree, GetLower(search[0].starty), GetUpper(search[0].endy));
if (!res) break;
}else if (search[1].x <= lines[i].x)
break;
}
if (res) printf("Yes\n");
else printf("No\n");
return 0;
}
分享到：
相关推荐
原理就大概如图所示，线段树的每个节点都是原数组的一段区间和，而叶子节点就是原数组对应 的值 建树代码： void build(int p,int lf,int rt){//建树 ans[p]=0; if(lf==rt) { ans[p]=A[lf]; return ; } int mid...
易语言源码易语言判断矩形重合源码.rar
本程序使用C++，红黑树实现线段重叠问题的查找，程序中有详细的注释，方便阅读。
易语言判断矩形重合源码,判断矩形重合,矩形是否定区域内,创建矩形
查找重叠于某点所有区间的一种数据结构 是一个线段树.对数轴查询很有帮助
时针与分针重合的C#代码。时针与分针重合的C#代码。时针与分针重合的C#代码
自动重合闸动作时间的整定原则 （1）单侧电源所采用的三相重合闸时间，除应大于故障点熄弧时间及周围介质去游离的时间外，还应大于断路器及操动机构复归原状准备好再次动作的时间。 （2）双侧电源线路的自动重合闸...
canvas类似画板的功能，在地图上选择区域。判断重合、覆盖、交叉。 可回显
java 判断两个时间段是否重叠的案例.docx
在MATLAB中调用，两个多面体输入形式可以是各自的顶点竖向量集合，也可以是MATLAB规定的线性规划条件形式，输出为重叠体各个...此程序用来MATLAB建模中判断两个空间体是否重叠，重叠体积的计算，comsol 的导入和仿真
2. 判断两点是否重合 1 3. 矢量叉乘 1 4. 矢量点乘 2 5. 判断点是否在线段上 2 6. 求一点饶某点旋转后的坐标 2 7. 求矢量夹角 2 ㈡ 线段及直线的基本运算 1. 点与线段的关系 3 2. 求点到线段所在直线垂线的...
基于数字信号处理芯片和复杂可编程逻辑器件的永磁重合器的研究与设计.pdf
2. 判断两点是否重合 3. 矢量叉乘 4. 矢量点乘 5. 判断点是否在线段上 6. 求一点饶某点旋转后的坐标 7. 求矢量夹角 ㈡ 线段及直线的基本运算 1. 点与线段的关系 2. 求点到线段所在直线垂线的垂足 3. 点到线段的最近...
重合指数学过密码学的人都知道计算他的重要性，python实现又快又好
自适应重合闸技术的研究，相当好的资料
计算两张图像的重合率，如果有一个标准数据集，一个程序计算的数据集，计算两个数据集的准确率、召回率及F1-measure；将两个图像进行点乘，重叠区域面积S，标准数据集面积S1，程序计算得到的数据集面积S2，则召回率=...
输电线路自动重合闸装置的作用和应满足的基本要求，单侧电源线路自动重合闸装置的接线及工作原理，双侧电源线路自动重合闸装置应考虑的特殊问题及无电压检定和同步检定的三相自动重合闸的工作原理，自动重合闸与继电...
电力系统自动重合闸matlab仿真.pdf
在一天的24小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次？都分别是什么时间？你怎样算出来的？
重合指数法的研究，谢清霞，于灏，本文主要研究了重合指数法的历史背景、来源、基本原理及其应用。并结合重合指数法，介绍了Vigenère密码和Kasiski测试法的相关知识。��