竞赛讨论区 > D题直接判断相交的解法
头像
LiSaiBo
编辑于 11-02 22:47 河南
+ 关注

D题直接判断相交的解法

#include <bits/stdc++.h>

using namespace std;

// 判断相交
bool check(int l1, int r1, int l2, int r2)
{
    if((l2 < l1 && r1 < r2) || (l1 < l2 && r2 < r1)) return false;
    else if(r1 < l2 || l1 > r2) return false;
    else return true;
}

void solve()
{
	int n; cin >> n;
    vector<pair<int, int>> a(n);    
    for(auto& [x, y] : a) cin >> x >> y;
    
  	// 直接升序默认排,first小就小,first相等,second小就小
    sort(a.begin(), a.end());
    
    for(int i = 0; i < n - 1; ++i)
    {
        int l1 = a[i].first, r1 = a[i].second;
        int l2 = a[i + 1].first, r2 = a[i + 1].second;
        if(!check(l1, r1, l2, r2)) // 判断相邻是否相交
        {
            cout << "No\n";
            return;
        }
    }
  	// 到了这里如果直接提交120分,因为我们只判断了相邻的情况
  	// 题目上是要求任意两两相交
  
  	// 判断首尾是否相交,如果首尾相交,那必定任意两两相交   
  	// 如果画图后觉得这个结论是错的,就想想排序是怎么排的
    int l1 = a[0].first, r1 = a[0].second;
    int l2 = a[n - 1].first, r2 = a[n - 1].second;
    if(check(l1, r1, l2, r2)) cout << "Yes\n";
    else cout << "No\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int T; cin >> T;
	while(T--)
	{
		solve();
	}

	return 0;
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐