Submission #1379118

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;

#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define rev(i,a,b) for(ll i=a;i>=b;i--)
#define pll pair<ll,ll>
#define vll vector<ll>
#define sll set<ll>
#define vpll vector<pll>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define ln length()
#define M 1000000007
ll r,c,n;
vector<pair<pll,pll> >lines;

// Given three colinear points p, q, r, the function checks if
// point q lies on line segment 'pr'
bool onSegment(pll p, pll q, pll r)
{
    if (q.F <= max(p.F, r.F) && q.F >= min(p.F, r.F) &&
        q.S <= max(p.S, r.S) && q.S >= min(p.S, r.S))
       return true;

    return false;
}

// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
ll orientation(pll p, pll q, pll r)
{
    // See http://www.geeksforgeeks.org/orientation-3-ordered-points/
    // for details of below formula.
    int val = (q.S - p.S) * (r.F - q.F) -
              (q.F - p.F) * (r.S - q.S);

    if (val == 0) return 0;  // colinear

    return (val > 0)? 1: 2; // clock or counterclock wise
}

// The main function that returns true if line segment 'p1q1'
// and 'p2q2' intersect.
bool intersect(pll p1, pll q1, pll p2, pll q2)
{
    // Find the four orientations needed for general and
    // special cases
    ll o1 = orientation(p1, q1, p2);
    ll o2 = orientation(p1, q1, q2);
    ll o3 = orientation(p2, q2, p1);
    ll o4 = orientation(p2, q2, q1);

    // General case
    if (o1 != o2 && o3 != o4)
        return true;

    // Special Cases
    // p1, q1 and p2 are colinear and p2 lies on segment p1q1
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;

    // p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;

    // p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;

     // p2, q2 and q1 are colinear and q1 lies on segment p2q2
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

    return false; // Doesn't fall in any of the above cases
}

bool check(){
    vector<pair<pll,ll> > pts;
    map<pll,pll> getright,getleft;
    for(auto xp:lines) pts.pb(mp(xp.F,1)),pts.pb(mp(xp.S,2)),getright[xp.F]=xp.S,getleft[xp.S]=xp.F;
    sort(pts.begin(),pts.end());
    set<pair<ll,pair<pll,pll> > > active;
    for(auto xp:pts){
        if(xp.S == 1){
            pll xpr = getright[xp.F];
            pair<pll,pll> line = mp(xp.F,xpr);
            ll yc = xp.F.S;
            active.insert(mp(yc,line));

            auto it = active.lower_bound(mp(yc,line));

            it++;
            if(it!=active.end()){
                auto idk = *it;
                pair<pll,pll> line2 = idk.S;
                if(intersect(line2.F,line2.S,line.F,line.S)) return false;
            }
            it--;

            if(it!=active.begin()){
                it--;
                auto idk = *it;
                pair<pll,pll> line2 = idk.S;
                if(intersect(line2.F,line2.S,line.F,line.S)) return false;
            }
        }
        else{
            pll xpl = getleft[xp.F];
            pair<pll,pll> line = mp(xpl,xp.F);
            ll yc = xpl.S;
            active.erase(mp(yc,line));

            auto it = active.lower_bound(mp(yc,line));
            if(it==active.end() || it == active.begin()) continue;

            auto idk = *it;
            pair<pll,pll> line2 = idk.S;

            it--;
            auto idk2 = *it;
            pair<pll,pll> line3 = idk2.S;
            if(intersect(line2.F,line2.S,line3.F,line3.S)) return false;
        }
    }

    return true;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>r>>c>>n;
    rep(i,1,n){
        ll a1,b1,a2,b2;cin>>a1>>b1>>a2>>b2;
        if ((a1 == 0 || a1 == r || b1 == 0 || b1 == c) && (a2 == 0 || a2 == r || b2 == 0 || b2 == c))
            lines.pb(mp(mp(a1,b1),mp(a2,b2)));
        /*if(a1 == 0 && a2!=0 && (a2 == r || b2 == 0 || b2 == c)) lines.pb(mp(mp(a1,b1),mp(a2,b2)));
        else if(a1 == r && a2!=r && (a2 == 0 || b2 == 0 || b2 == c)) lines.pb(mp(mp(a1,b1),mp(a2,b2)));
        else if(b1 == 0 && b2!=0 && (b2 == c || a2 == 0 || a2 == r)) lines.pb(mp(mp(a1,b1),mp(a2,b2)));
        else if(b1 == c && b2!=c && (b2 == 0 || a2 == 0 || a2 == r)) lines.pb(mp(mp(a1,b1),mp(a2,b2)));*/
    }
    if(lines.size()<=1){
        cout<<"YES"<<endl;
        return 0;
    }
    n=lines.size();
    if(check()) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

Submission Info

Judge Result