Решение задачи Прогулка с Codeforces

Без пояснения   Просмотров: 1055

У Алисы есть миленькая кошечка. Чтобы кошка была в форме, Алиса хочет спланировать маршрут для прогулки кошки.

Изначально, кошка Алиса находится в ячейке (x,y) на бесконечном клетчатом поле. По теории Алисы кошка должна пройти:

ровно a шагов влево: из (u,v) в (u−1,v);
ровно b шагов вправо: из (u,v) в (u+1,v);
ровно c шагов вниз: из (u,v) в (u,v−1);
ровно d шагов вверх: из (u,v) в (u,v+1).
Обратите внимание, что шаги можно делать в произвольном порядке. Например, если кошка должна сделать 1 шаг влево, 3 шага вправо и 2 шага вниз, то маршрут вправо, вниз, влево, вправо, вправо, вниз корректный.

С другой стороны, Алиса волнуется, что кошка может потеряться, если уйдет очень далеко от нее. Поэтому она надеется, что ее кошка всегда находится в области [x1,x2]×[y1,y2], то есть для любой позиции (u,v) маршрута выполняется x1≤u≤x2 и y1≤v≤y2.

Также обратите внимание, что кошка может посещать одну и ту же клетку несколько раз.

Помогите Алисе понять, существует ли маршрут, который удовлетворяет ее желаниям.

Формально, путь должен состоять ровно из a+b+c+d единичных шагов (a влево, b вправо, c вниз, d вверх). Алиса может совершать шаги в любом порядке. Её текущая позиция (u,v) всегда должна удовлетворять ограничениям: x1≤u≤x2, y1≤v≤y2. Путь начинается из точки (x,y).

Требуется решить задачу для t наборов входных данных независимо друг от друга.

Код 

#include <bits/stdc++.h>

using namespace std;

int main()
{
    //ifstream fin("input.txt");
    //ofstream fout("output.txt");
    long long a,b,c,d,x,x1,x2,y,y1,y2;
    int t;
    cin >> t;
    for(unsigned i = 0; i < t; ++i) {
        cin>>a>>b>>c>>d>>x>>y>>x1>>y1>>x2>>y2;
        int amax=(a-b)*-1;
        int cmax=(c-d)*-1;
        if(x1==x2 && (a+b)>0){
            cout << "NO" << endl;
            continue;
        }
        if(y1==y2 && (c+d)>0){
            cout << "NO" << endl;
            continue;
        }
        x+=amax;
        y+=cmax;
        if((x>=x1 && x<=x2) && (y>=y1 && y<=y2)){
            cout << "YES";
        }
        else{
            cout << "NO";
        }
        cout << endl;
    }
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp