Submission #3416085

---

Source Code Expand

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define of(i,l,r) for(int i=l;i>=r;i--)
#define fe(i,u) for(int i=head[u];i;i=e[i].next)
using namespace std;
typedef long long ll;
#define P(a,b) make_pair(a,b)
inline void open(const char *s)
{
	#ifndef ONLINE_JUDGE
	char str[20];
	sprintf(str,"in%s.txt",s);
	freopen(str,"r",stdin);
//	sprintf(str,"out%s.txt",s);
//	freopen(str,"w",stdout);
	#endif
}
inline int rd()
{
	static int x,f;
	x=0;f=1;
	char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
	return f>0?x:-x;
}
const int N=100010;
int R,C,n,tot=0;
struct line{int x1,y1,x2,y2;}a[N];
struct point{int x,y;point(int x=0,int y=0):x(x),y(y){}}p[N<<1];
inline bool operator<(point a,point b){return P(a.x,a.y)<P(b.x,b.y);}
vector<line>b[6];

inline bool cmp1(line a,line b){return a.x1<b.x1;}
inline bool cmp2(line a,line b){return a.y1<b.y1;}

inline void vpush(line a)
{
	if(P(a.x1,a.y1)>P(a.x2,a.y2))swap(a.x1,a.x2),swap(a.y1,a.y2);
	if(!a.y1&&a.y2==C){b[0].push_back(a);return;}
	if(!a.x1&&a.x2==R){b[1].push_back(a);return;}
	if(!a.x1&&!a.y2){b[2].push_back(a);return;}
	if(!a.y1&&a.x2==R){b[3].push_back(a);return;}
	if(a.y1==C&&a.x2==R){b[4].push_back(a);return;}
	if(!a.x1&&a.y2==C){b[5].push_back(a);return;}
}

inline bool gao1()
{
	if(b[0].size()>0&&b[1].size()>0)return 0;
	if(b[0].size()>0){
		int p=b[0].size()-1;
		if(b[2].size()>0){
			int siz=b[2].size()-1;
			if(b[2][siz].x2>b[0][0].x1)return 0;
		}
		if(b[5].size()>0){
			if(b[5][0].x2>b[0][0].x2)return 0;
		}
		if(b[3].size()>0){
			if(b[3][0].x1<b[0][p].x1)return 0;
		}
		if(b[4].size()>0){
			if(b[4][0].x1<b[0][p].x2)return 0;
		}
	}
	else if(b[1].size()>0){
		int p=b[1].size()-1;
		if(b[2].size()>0){
			int siz=b[2].size()-1;
			if(b[2][siz].y1>b[1][0].y1)return 0;
		}
		if(b[3].size()>0){
			if(b[3][0].y2>b[1][0].y2)return 0;
		}
		if(b[4].size()>0){
			if(b[4][0].y2<b[1][p].y2)return 0;
		}
		if(b[5].size()>0){
			if(b[5][0].y1<b[1][p].y1)return 0;
		}
	}
	return 1;
}

inline bool gao3()
{
	if(b[2].size()==0)return 1;
	if(b[3].size()==0)return 1;
	int p=b[2].size()-1;
	if(b[2][p].x1>b[3][0].x1)return 0;
	return 1;
}

inline bool gao4()
{
	if(b[3].size()==0)return 1;
	if(b[4].size()==0)return 1;
	int p=b[3].size()-1;
	if(b[3][p].y2>b[4][0].y2)return 0;
	return 1;
}

inline bool gao5()
{
	if(b[4].size()==0)return 1;
	if(b[5].size()==0)return 1;
	if(b[4][0].x1<b[5][0].x2)return 0;
	return 1;
}

inline bool gao6()
{
	if(b[5].size()==0)return 1;
	if(b[2].size()==0)return 1;
	int p=b[2].size()-1;
	if(b[2][p].y1>b[5][0].y1)return 0;
	return 1;
}

inline bool gao()
{
	sort(p+1,p+tot+1);
	fo(i,1,tot-1)if(p[i].x==p[i+1].x&&p[i].y==p[i+1].y)return 0;
	int siz;
	sort(b[0].begin(),b[0].end(),cmp1);
	siz=b[0].size()-1;
	fo(i,0,siz-1)if(b[0][i+1].x2<b[0][i].x2)return 0;
	
	sort(b[1].begin(),b[1].end(),cmp2);
	siz=b[1].size()-1;
	fo(i,0,siz-1)if(b[1][i+1].y2<b[1][i].y2)return 0;
	
	sort(b[2].begin(),b[2].end(),cmp2);
	siz=b[2].size()-1;
	fo(i,0,siz-1)if(b[2][i+1].x2<b[2][i].x2)return 0;
	
	sort(b[3].begin(),b[3].end(),cmp1);
	siz=b[3].size()-1;
	fo(i,0,siz-1)if(b[3][i+1].y2>b[3][i].y2)return 0;
	
	sort(b[4].begin(),b[4].end(),cmp1);
	siz=b[4].size()-1;
	fo(i,0,siz-1)if(b[4][i+1].y2<b[4][i].y2)return 0;
	
	sort(b[5].begin(),b[5].end(),cmp2);
	siz=b[5].size()-1;
	fo(i,0,siz-1)if(b[5][i+1].x2>b[5][i].x2)return 0;
	
	if(!gao1())return 0;
	if(!gao3())return 0;
	if(!gao4())return 0;
	if(!gao5())return 0;
	if(!gao6())return 0;
		
	return 1;
}

int main()
{
	R=rd();C=rd();n=rd();
	fo(i,1,n){
		a[i].x1=rd();a[i].y1=rd();a[i].x2=rd();a[i].y2=rd();
		p[++tot]=point(a[i].x1,a[i].y1);
		p[++tot]=point(a[i].x2,a[i].y2);
	}
	fo(i,1,n)vpush(a[i]);
	if(gao())puts("YES");
	else puts("NO");
	return 0;
}

Submission Info

Judge Result