C++题解(17) 狐猬编程: 640.线段覆盖

题目描述

在一条数轴上，有N条线段，第i条线段的左端点是s[i]，右端点是e[i]。如果线段有重叠（即使是端点重叠也算是重叠），则输出“impossible”， 如果没有重叠则输出“possible”。

输入格式

输入文件名：640.in

多组测试数据。

第一行，一个整数G，表示有G组测试数据。1 <= G <= 10。

每组测试数据格式如下：

第一行，一个整数N。  1 <= N <= 10。

接下来有N行，每行两个整数：s[i]，e[i]。  0<=s[i],e[i]<=1000000。

输出格式

输出文件名：640.out

共G行，每行一个字符串，不含双引号。

输入/输出例子1

输入：

5

3

10 47

100 235

236 347

3

100 235

236 347

10 47

2

10 20

20 30

3

10 20

400000 600000

500000 700000

4

1 1000000

40 41

50 51

60 61

输出：

possible

possible

impossible

impossible

impossible

 解题思路

        我们可以判段前一段右端点是否大于当前这段的左端点，如果是，证明两条线段相交了。

参考答案 

#include <iostream> 
#include <algorithm>
using namespace std;
 
struct String //string 在这里是 线 的意思
{
	int left;//左端点
	int right;//右端点
}a[11];
 
bool cmp(String a,String b)//给线段端点排序，方便判断是否相交
{
	return a.right<b.right;
}
 
int main()
{
	int t,n;
	cin>>t;
	for(int j=1;j<=t;j++)
	{
		cin>>n;
		for(int i=1;i<=n;i++)//输入左、右端点
		{
			cin>>a[i].left>>a[i].right;
		}
 
		sort(a+1,a+n+1,cmp);
 
		int l=1;//用来放适合判断的数据位置
		bool f=true;
		for(int i=2;i<=n;i++)
		{
			if(a[l].right<a[i].left)l=i;//更新l
			else //相交了
			{
				f=false;
				break;
			}
		}
 
		if(f==true)cout<<"possible"<<endl;//没有相交
		else cout<<"impossible"<<endl;//相交了
	}
 
	return 0;
}