ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1454. Прямоугольники 2

accepted
Послано Mikhail 31 май 2018 01:19
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define re return
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define pi (3.14159265358979323846264338327950288419716939937510)
#define fo(i, n) for(int i = 0; i < n; ++i)
#define ro(i, n) for(int i = n - 1; i >= 0; --i)
#define unique(v) v.resize(unique(all(v)) - v.begin())

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }
template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef double D;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree;

const int maxn = 5;
int sz[2][maxn];
bool how[maxn];
int pos1[maxn], pos2[maxn];

bool check_intersection () {
    bool check = true;
    fo(i, 5) {
        fo(j, i) {
            check = false;
            if (pos1[i] + sz[how[i]][i] <= pos1[j]) check = true;
            if (pos1[j] + sz[how[j]][j] <= pos1[i]) check = true;
            if (pos2[i] + sz[!how[i]][i] <= pos2[j]) check = true;
            if (pos2[j] + sz[!how[j]][j] <= pos2[i]) check = true;
            if (!check) re false;
        }
    }
    re true;
}

bool check_area () {
    int x = -1, y = -1;
    fo(i, 5) {
        x = max(x, pos1[i] + sz[how[i]][i]);
        y = max(y, pos2[i] + sz[!how[i]][i]);
    }
    int s1 = 0, s2 = x * y;
    fo(i, 5) s1 += sz[0][i] * sz[1][i];
    re s1 == s2;
}

bool major_check() {
    bool ans = check_area() && check_intersection();
    re ans;
}

vector <pair <ii, bool> > v;

bool f (int mask) {
    if (__builtin_popcount(mask) == 5) re major_check();
    fo(a, 5) {
        if (((1 << a) & mask) == 0) {
            fo(q, 2) {
                how[a] = q;
                fo(i, v.size()) {
                    if (v[i].se) continue;
                    ii j = v[i].fi;
                    v[i].se = true;
                    v.pb(mp(mp(j.fi + sz[how[a]][a], j.se), false));
                    v.pb(mp(mp(j.fi, j.se + sz[!how[a]][a]), false));
                    pos1[a] = j.fi;
                    pos2[a] = j.se;
                    if (f(mask | (1 << a))) re true;
                    v[i].se = false;
                    v.pop_back();
                    v.pop_back();
                }
            }
        }
    }
    re false;
}

int main() {
    fo(i, 5) fo(j, 2) cin >> sz[j][i];
    v.eb(mp(0, 0), 0);
    if (f(0)) cout << "YES" << endl;
    else cout << "NO" << endl;
}