时间戳

首页 > 技术文章 > AtCoder Regular Contest 076 E - Connected?

AtCoder Regular Contest 076 E - Connected?

mgz- 2017-07-07 20:46 原文

E - Connected?

Time limit : 2sec / Memory limit : 256MB

Score : 700 points

Problem Statement

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

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

Output

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

Sample Input 1

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

Sample Output 1

Copy
YES

The above figure shows a possible solution.

Sample Input 2

Copy
2 2 4
0 0 2 2
2 0 0 1
0 2 1 2
1 1 2 1

Sample Output 2

Copy
NO

Sample Input 3

Copy
5 5 7
0 0 2 4
2 3 4 5
3 5 5 2
5 5 5 4
0 3 5 1
2 2 4 4
0 5 4 1

Sample Output 3

Copy
YES

Sample Input 4

Copy
1 1 2
0 0 1 1
1 0 0 1

Sample Output 4

Copy
NO

 注意x,y的顺序

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<cmath>
#include<set>
#include<stack>
#define ll long long
#define pb push_back
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
#define cls(name,x) memset(name,x,sizeof(name))
using namespace std;
const int inf=1e9+10;
const ll llinf=1e16+10;
const int maxn=1e5+10;
const int maxm=2e5+10;
const int mod=1e9+7;
int n,m,k;
pair<int,int> point[4][maxn];
int c[4];
bool judge(int x,int y)
{
    if(x==0||y==0||x==m||y==n)
        return true;
    return false;
}
void func(int x,int y,int t)
{
    if(y==0)
        point[0][c[0]++]=make_pair(x,t);
    else if(x==m)
        point[1][c[1]++]=make_pair(y,t);
    else if(y==n)
        point[2][c[2]++]=make_pair(x,t);
    else if(x==0)
        point[3][c[3]++]=make_pair(y,t);
}
bool cmp(const pair<int,int> &a,const pair<int,int> &b)
{
    return a.first>b.first;
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(~scanf("%d %d %d",&n,&m,&k))
    {
        int flag=1;
        cls(c,0);
        for(int i=1;i<=k;i++)
        {
            int x1,y1,x2,y2;
            scanf("%d %d %d %d",&y1,&x1,&y2,&x2);
            if(judge(x1,y1)&&judge(x2,y2))
            {
                func(x1,y1,i);
                func(x2,y2,i);
            }
        }
        sort(point[0],point[0]+c[0]);
        sort(point[1],point[1]+c[1]);
        sort(point[2],point[2]+c[2],cmp);
        sort(point[3],point[3]+c[3],cmp);
        stack<int> S;
        for(int i=0;i<4;i++)
            for(int j=0;j<c[i];j++)
            {
                if(S.empty())
                    S.push(point[i][j].second);
                else
                {
                    if(S.top()==point[i][j].second)
                        S.pop();
                    else S.push(point[i][j].second);
                }
            }
        if(!S.empty()) flag=0;
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

 

推荐阅读