Hello 2020 D - New Year and Conference （线段交集）

?? ?? ??

题意：给出n对sa，ea，sb，eb，要求在a,b上要不然都相交，要不然都不相交

1，a相交 ---> b相交，a不相交 ---> b不相交 （即b相交--->a相交）

2，枚举a的端点，将对应的b线段放到集合中，如果multiset中还有元素（即当前枚举的a段与之前有重叠），检查b是否与之前的全部重叠，出现不重叠的情况只可能是当前左端点大于最小的右端点或当前右端点小于最大的左端点

bool can(vector<pair<int,pii> > event,vector<pii> data)
{
    sort(all(event));
    multiset <int>start,end;
    rep(i,event.size())
    {
        int pos = event[i].second.second;//当前事件对应的b段的下标
        int l=data[pos].first,r=data[pos].second;
        if(event[i].second.first==0)
        {//插入结点前判断是否合格
            if(start.size()&& ( l > *end.begin() || r < *start.rbegin()))  return false;
            start.insert(l),end.insert(r);
        }
        else   start.erase(start.find(l)),end.erase(end.find(r));
    }
    return true;
}
int main()
{
    int n;cin>>n;
    vector<pair<int,pii>> event1,event2;
    vector<pii>data1,data2;
    rep(i,n)
    {
        int sa,ea,sb,eb;cin>>sa>>ea>>sb>>eb;
        event1.push_back(make_pair(sa,make_pair(0,i)));
        event1.push_back(make_pair(ea,make_pair(1,i)));
        data1.push_back(make_pair(sb,eb));
        event2.push_back(make_pair(sb,make_pair(0,i)));
        event2.push_back(make_pair(eb,make_pair(1,i)));
        data2.push_back(make_pair(sa,ea));
    }
    puts(can(event1,data1) && can(event2,data2)?"YES":"NO");
    //stop;
    return 0;
}

Hello 2020 D - New Year and Conference （线段交集）

原文：https://www.cnblogs.com/Herlo/p/12218505.html