Submission #3806094

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 1000000000
#define LLINF 100000000000000000ll
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
ll add(ll a,ll b){
	return a+b;
}
struct P{
	ll x,y;
	int val;
	P() {}
	P(ll x,ll y):x(x),y(y){}
	P(ll x,ll y,int val):x(x),y(y),val(val){}
	P operator +(P p){
		return P(add(x,p.x),add(y,p.y));
	}
	P operator -(P p){
		return P(add(x,-p.x),add(y,-p.y));
	}
	P operator *(double d){
		return P(d*x,d*y);
	}
	ll dot(P p){
		return add(x*p.x,y*p.y);
	}
	ll det(P p){
		return add(x*p.y,-y*p.x);
	}
};

int R,C,N;
int M;
P ps[100100];
bool used[100100];
bool Xedge(int x){
	if(x==0||x==R)return true;
	else return false;
}
bool Yedge(int y){
	if(y==0||y==C)return true;
	else return false;
}
pair<ll,ll> idx(P a){
	pair<ll,ll> ret;
	if(a.y==0ll&&a.x<R){
		ret.fi=0;ret.sec=a.x;
	}else if(a.x==R&&a.y<C){
		ret.fi=1;ret.sec=a.y;
	}else if(a.y==C&&a.x>0ll){
		ret.fi=2;ret.sec=R-a.x;
	}else{
		ret.fi=3;ret.sec=C-a.y;
	}
	return ret;
}
bool comp(const P& p,const P& q){
	return idx(p)<idx(q);
}
int main(){
	cin >> R >> C >> N;
	for(int i=0;i<N;i++){
		int x1,y1,x2,y2;
		cin >> x1 >> y1 >> x2 >> y2;
		if((Xedge(x1)||Yedge(y1))&&(Xedge(x2)||Yedge(y2))){
			ps[2*M]=P(x1,y1,i+1);
			ps[2*M+1]=P(x2,y2,i+1);
			M++;
		}
	}
	M*=2;
	sort(ps,ps+M,comp);
	//vector<P> ch = convex_hull(ps,M);
	//assert(ch.size()==M);
	/*for(int i=0;i<M;i++){
		cout << ps[i].x << ' ' << ps[i].y << ' ' << ps[i].val << endl;
 	}*/
 	stack<int> s;
 	for(int i=0;i<M;i++){
 		int c = ps[i].val;
 		if(used[c]){
 			if(s.top()!=c){
 				printf("NO\n");
 				return 0;
 			}
 			s.pop();
 		}else{
 			s.push(c);
 			used[c]=true;
 		}
 	}
 	printf("YES\n");
	return 0;
}

Submission Info

Judge Result