题目描述
在一条数轴上,有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
解题思路
我们可以判段前一段右端点是否大于当前这段的左端点,如果是,证明两条线段相交了。
标签:10,17,输出,int,题解,线段,C++,端点,impossible From: https://blog.csdn.net/2301_78151773/article/details/140753970参考答案
#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; }