@UPC @AtCoder Regular Contest 076 E:Connected?（思维）

Snuke is playing a puzzle game. In this game, you are given a rectangular board of dimensions R×C, filled with numbers. Each integer i from 1 through N is written twice, at the coordinates (xi,1,yi,1) and (xi,2,yi,2).
The objective is to draw a curve connecting the pair of points where the same integer is written, for every integer from 1 through N. Here, the curves may not go outside the board or cross each other.
Determine whether this is possible.

Constraints
1≤R,C≤108
1≤N≤105
0≤xi,1,xi,2≤R(1≤i≤N)
0≤yi,1,yi,2≤C(1≤i≤N)
All given points are distinct.
All input values are integers.

 

输入

Input is given from Standard Input in the following format:
R C N
x1,1 y1,1 x1,2 y1,2
:
xN,1 yN,1 xN,2 yN,2

 

输出

Print YES if the objective is achievable; print NO otherwise.

 

样例输入

4 2 3
0 1 3 1
1 1 4 1
2 0 2 2

 

样例输出

YES

 

提示

The above figure shows a possible solution.

 

[题意]

问是否可以连线,,

很容易注意到 当两个点都在内部时,  无论如何都是可以的,  只有 两个点都在边缘时,  形成的线段. 构成相交 ,此时

无论如何 都是 不可以的.

起初 直接上的 几何模板 ,两个线段判断相交跨立实验 .. 然后GG

这种情况时,  应该是可以的, 但是 两个线段 共线,     然后GG

,然后用 栈模拟一波.  左右括号匹配  , 类似///

 

[代码]

#include <iostream>
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i = n;i>=a;i--)

#define Si(x) scanf("%d",&x)
#define Pi(x) printf("%d\n",x)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;



using namespace std;
typedef pair<int,int> PAIR;
const int maxn = 1e5+10;

int n;
double r,c;

bool check(int x, int y){
  if(x == 0 || x == r || y == 0 || y == c) return true;
  return false;
}
vector<pair<int,int> >v[4];
void add(int idex,int x,int y)
{
    if(x==0) v[0].pb( mp(idex,y));
    else if( x== r) v[2].pb(mp(idex,y));
    else if( y == 0) v[3].pb(mp(idex,x));
    else if ( y== c) v[1].pb(mp(idex,x));
}
int cmp(PAIR p1, PAIR p2)
{
    return p1.se < p2.se;
}
int cmp2(PAIR p1,PAIR p2)
{
    return p1.se > p2.se;
}
int main()
{

    scanf("%lf %lf",&r,&c);
    Si(n);
    int flag = 0;
    int k=0;
    rep(i,1,n)
    {
        double x1,x2,y1,y2;

        scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
        if( check(x1,y1) && check(x2,y2))
        {
            add(i,x1,y1);
            add(i,x2,y2);
        }
    }
    sort(v[0].begin(),v[0].end(),cmp);
    sort(v[1].begin(),v[1].end(),cmp);

    sort(v[2].begin(),v[2].end(),cmp2);
    sort(v[3].begin(),v[3].end(),cmp2);

    stack<int> St;
    for(int i = 0 ; i <4 ;i++)
    {
        for(int j = 0; j < v[i].size(); j++)
        {
            //cout<<v[i][j].first<<endl;
            if(St.size()==0 )
            {

                St.push(v[i][j].fi);
                continue;
            }
            if(St.top() == v[i][j].fi)
                St.pop();
            else
                St.push(v[i][j].fi);
        }
    }
    if(St.empty())
    {
        printf("YES\n");
    }
    else
        printf("NO\n");



    /*
4 2 3
0 1 4 1
1 1 4 1
2 0 2 2
4 2 3
0 1 3 0
1 1 4 1
1 0 3 0
    */

    return 0;
}