Codeforces Round #535 Div.3 题解

（更新ing）

C. Robot Breakout

题目大意：一个边界xy坐标为-1e5~1e5的地图上有n个已知坐标的机器人，每个机器人可以无限次执行向上下左右走一格的某几个（0~4个）操作。问是否存在一个点，所有机器人都可以移动到那里。存在输出1和这个点的坐标，不存在输出0

题解：2000人A的题居然不会，好菜啊（还好没打这一场
比较显然的一步是通过每个机器人的操作限制和当前坐标可以得到他能够走到的范围
于是陷入二维修改查询无法自拔。。。
实际上只需要记录一下最小最大xy就可以了……
xy分开考虑是这类题的常见思想

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

int max(int a, int b){return a > b ? a : b;}
int min(int a, int b){return a < b ? a : b;}
void swap(int &a, int &b){int tmp = a;a = b;b = tmp;}
int lowbit(int &x){return x & (-x);}
void read(int &x)
{
    x = 0;char ch = getchar(), c = ch;
    while(ch < '0' || ch > '9') c = ch, ch = getchar();
    while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
    if(c == '-') x = -x;
}

const int INF = 100000;

int q, n, mi_x, ma_x, mi_y, ma_y;

int main()
{
    read(q);
    for(;q;--q)
    {
        mi_x = mi_y = -INF, ma_x = ma_y = INF;
        read(n);
        for(int i = 1;i <= n;++ i)
        {
            int tmpx, tmpy;
            read(tmpx), read(tmpy);
            int tmp1, tmp2, tmp3, tmp4;
            read(tmp1), read(tmp2), read(tmp3), read(tmp4);
            if(tmp1 == 0) mi_x = max(mi_x, tmpx);
            if(tmp2 == 0) ma_y = min(ma_y, tmpy);
            if(tmp3 == 0) ma_x = min(ma_x, tmpx);
            if(tmp4 == 0) mi_y = max(mi_y, tmpy);
        }
        if(mi_x > ma_x || mi_y > ma_y) printf("0\n");
        else printf("1 %d %d\n", mi_x, mi_y);
    }
    return 0;
}

Codeforces Round #535 Div.3

原文：https://www.cnblogs.com/huibixiaoxing/p/11298667.html