Submission #2105442

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;


typedef long long nyan;
typedef pair<nyan,nyan> P;
typedef pair<P,P> P2;

nyan r,c;
int n;

P p1[100010];
P p2[100010];


bool on_edge(nyan a,nyan b)
{
	return a == 0 || a == r || b == 0 || b == c;
}


nyan edge_point(P p)
{
	if(p.second == 0)
	{
		return p.first;
	}
	if(p.first == r)
	{
		return r + p.second;
	}
	if(p.second == c)
	{
		return r + c + r - p.first;
	}
	if(p.first == 0)
	{
		return r + c + r + c - p.second;
	}
	return -1;
}

vector<nyan> xs,ys;

int imos[800010];

int main()
{
	cin >> r >> c >> n;


	xs.push_back(0);
	xs.push_back(r);
	ys.push_back(0);
	ys.push_back(c);

	for(int i = 0;i < n;i++)
	{
		cin >> p1[i].first >> p1[i].second >> p2[i].first >> p2[i].second;

		xs.push_back(p1[i].first);
		xs.push_back(p2[i].first);
		ys.push_back(p1[i].second);
		ys.push_back(p2[i].second);
	}

	sort(xs.begin(),xs.end());
	sort(ys.begin(),ys.end());

	xs.erase(unique(xs.begin(),xs.end()),xs.end());
	ys.erase(unique(ys.begin(),ys.end()),ys.end());
	
	r = xs.size() - 1;
	c = ys.size() - 1;

	vector<P> e_set;
	
	for(int i = 0;i < n;i++)
	{
		int x1,y1,x2,y2;

		x1 = lower_bound(xs.begin(),xs.end(),p1[i].first) - xs.begin();
		y1 = lower_bound(ys.begin(),ys.end(),p1[i].second) - ys.begin();

		x2 = lower_bound(xs.begin(),xs.end(),p2[i].first) - xs.begin();
		y2 = lower_bound(ys.begin(),ys.end(),p2[i].second) - ys.begin();


		if(on_edge(x1,y1) && on_edge(x2,y2))
		{
			int e1 = edge_point(P(x1,y1));
			int e2 = edge_point(P(x2,y2));
			if(e1 > e2) swap(e1,e2);
          e_set.push_back(P(e1,e2));
			imos[e1]++;
			imos[e2 + 1]--;
		}
	}

	for(int i = 1;i < r * 2 + c * 2;i++)
	{
		imos[i] += imos[i - 1];
	}

	for(P e_s : e_set)
	{
		if(imos[e_s.first] != imos[e_s.second])
		{
			cout << "NO" << endl;
			return 0;
		}
	}



	cout << "YES" << endl;
	return 0;
}

Submission Info

Judge Result