#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")
using namespace std;
#define int ll
using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
using vll = vector<ll>;
const int INF = 1e9;
struct steak {
ii h, v;
bool inside(ii pct) {
return h.first <= pct.first && pct.first <= h.second
&& v.first <= pct.second && pct.second <= v.second;
}
};
tuple<int, int, int, int> get_steak_extremums(vector<steak> S) {
auto seg_extremums = [&](vector<ii> V) {
int l = -INF, r = INF;
for(auto [s, d] : V) {
l = max(l, s);
r = min(r, d);
}
return ii{l, r};
};
vector<ii> H, V;
for(auto [h, v] : S) {
H.push_back(h); V.push_back(v);
}
auto [lh, rh] = seg_extremums(H);
auto [lv, rv] = seg_extremums(V);
return {lh, rh, lv, rv};
}
vector<ii> sol_k1(vector<steak> S) {
auto [lh, rh, lv, rv] = get_steak_extremums(S);
if(lh <= rh && lv <= rv) return vector<ii>{ii{lh, lv}};
return vector<ii>();
}
vector<ii> sol_k2(vector<steak> S) {
///will return the solution if it satisfies everyone
auto [lh, rh, lv, rv] = get_steak_extremums(S);
vector<ii> re;
auto check_sol = [&](ii p1, ii p2) -> bool{
bool ok = true;
for(auto it : S) {
ok &= it.inside(p1) || it.inside(p2);
if(!ok) break;
}
if(ok) {
re = vector<ii>{p1, p2};
}
return ok;
};
check_sol(ii{lh, lv}, ii{rh, rv});
check_sol(ii{lh, rv}, ii{rh, lv});
return re;
}
vector<ii> sol_k3(vector<steak> S) {
///will return the solution if it satisfies everyone
auto [lh, rh, lv, rv] = get_steak_extremums(S);
vector<ii> Re;
auto check_rest = [&](ii p) {
vector<steak> LeftOver;
for(auto it : S)
if(!it.inside(p)) LeftOver.push_back(it);
auto Cur = sol_k2(LeftOver);
if(!Cur.empty()) {
Cur.push_back(p);
Re = Cur;
}
};
vector<ii> Corners = { {lh, lv}, {lh, rv}, {rh, lv}, {rh, rv}, };
for(auto it : Corners) check_rest(it);
return Re;
}
vector<pair<int, ii> > get_intersect(steak x, vector<ii> &Corners) {
///returns a vector of (edge id, (min max allowed))
auto get_overlap0 = [&](ii seg, int l, int r) {
if(l > r) swap(l, r);
return ii{max(l, seg.first), min(r, seg.second)};
};
auto inside_seg = [&](int p, ii seg) { return seg.first <= p && p <= seg.second; };
auto get_overlap = [&](ii p1, ii p2) {
if(p1.first == p2.first) {
if(inside_seg(p1.first, x.h))
return get_overlap0(x.v, p1.second, p2.second);
else return ii{1, 0};
} else {
if(inside_seg(p1.second, x.v))
return get_overlap0(x.h, p1.first, p2.first);
else
return ii{1, 0};
}
};
vector<pair<int, ii> > Re;
for(int i = 0; i < 4; ++i) {
auto re = get_overlap(Corners[i], Corners[(i + 1) % 4]);
if(re.first <= re.second) Re.push_back({i, re});
}
return Re;
}
ii intersect(ii a, ii b) {
return {max(a.first, b.first), min(a.second, b.second)};
}
struct RestrictionDS {
int n;
ii re;
vector<ii> Re;
vector<pair<ii, ii> > V;
void add(ii x1, ii x2) {
///if a in x1 -> b in x2
V.push_back({x1, x2});
}
void init(int N) {
n = N;
Re.resize(n, {-INF, INF});
vector<vector<ii> > Add(n), Rem(n);
for(auto [x1, x2] : V) {
auto [s, d] = x1;
Add[s].push_back(x2);
Rem[d].push_back(x2);
}
multiset<int> Low, High;
for(int i = 0; i < n; ++i) {
for(auto [l, r] : Add[i]) {
Low.insert(l);
High.insert(r);
}
int st = -INF, dr = INF;
if(!Low.empty()) st = *Low.rbegin();
if(!High.empty()) dr = *High.begin();
Re[i] = {st, dr};
for(auto [l, r] : Rem[i]) {
Low.erase(Low.find(l));
High.erase(High.find(r));
}
}
}
ii eval(int p) {
return Re[p];
}
};
vector<ii> sol_k4_special(vector<steak> S) {
vi X_posib, Y_posib;
for(auto [h, v] : S) {
X_posib.push_back(h.first); X_posib.push_back(h.second);
Y_posib.push_back(v.first); Y_posib.push_back(v.second);
}
auto norm_vec = [&](vi &V) -> pair<int, map<int, int> > {
sort(V.begin(), V.end());
V.resize(unique(V.begin(), V.end()) - V.begin());
int len = (int)V.size();
map<int, int> vti;
for(int i = 0; i < len; ++i) {
vti[V[i]] = i;
}
return {len, vti};
};
auto [len_x, vti_x] = norm_vec(X_posib);
auto [len_y, vti_y] = norm_vec(Y_posib);
for(auto &[h, v] : S) {
h.first = vti_x[h.first]; h.second = vti_x[h.second];
v.first = vti_y[v.first]; v.second = vti_y[v.second];
}
auto [lh, rh, lv, rv] = get_steak_extremums(S);
vector<ii> Corners = { {rh, rv}, {rh, lv}, {lh, lv}, {lh, rv}, };
vector<ii> FullSeg = { {rv, lv}, {rh, lh}, {rv, lv}, {rh, lh}, }; /// for negations
auto negate = [&](ii seg, ii full) {
assert(seg.first <= seg.second);
vector<ii> Rez;
if(seg.second < full.second) Rez.push_back({seg.second + 1, full.second});
if(full.first < seg.first) Rez.push_back({full.first, seg.first - 1});
return Rez;
};
vector<ii> RestrictiiInit;
for(int i = 0; i < 4; ++i) {
RestrictiiInit.push_back(FullSeg[i]);
}
array<array<RestrictionDS, 4>, 4> Forbid;
vi Order = {0, 3, 1, 2}, RankOrd = {0, 2, 3, 1};
for(auto x : S) {
int nrc = 0;
for(auto p : Corners) nrc += x.inside(p);
if(nrc > 1) { /// contains one whole edge; is surely covered
continue;
}
auto Inter = get_intersect(x, Corners);
assert(0 < Inter.size() && Inter.size() <= 2);
if(Inter.size() == 1) { ///simple restriction
///Basic[Inter[0].first].add(ii{0, 0}, Inter[0].second);
RestrictiiInit[Inter[0].first] = intersect(RestrictiiInit[Inter[0].first], Inter[0].second);
} else {
if(RankOrd[Inter[0].first] > RankOrd[Inter[1].first]) swap(Inter[0], Inter[1]);
auto [id0, seg0] = Inter[0]; auto [id1, seg1] = Inter[1];
for(auto it : negate(seg0, FullSeg[id0]))
Forbid[id0][id1].add(it, seg1);
if(id0 % 2 == id1 % 2 && id0 == 3) { /// grava
RestrictiiInit[id0] = intersect(RestrictiiInit[id0], {rh, seg1.second});
RestrictiiInit[id1] = intersect(RestrictiiInit[id1], {seg1.first, lh});
// Basic[id0].add({0, 0}, {rh, seg1.second});
// Basic[id1].add({0, 0}, {seg1.first, lh});
}
}
}
for(int i = 0; i < 4; ++i) {
for(int j = i + 1; j < 4; ++j) {
///Forbid[Ord[i]][Ord[j]]
if(Order[i] % 2 == 1) {
Forbid[Order[i]][Order[j]].init(len_x);
} else {
Forbid[Order[i]][Order[j]].init(len_y);
}
}
}
for(int x0 = 0; x0 < len_y; ++x0) {
///now choose the others greedly
vector<ii> Rest = RestrictiiInit;
vi X(4, 0);
X[0] = x0;
bool ok = true;
for(int i = 1; i < 4; ++i) {
for(int j = i; j < 4; ++j) { /// process what Order[i - 1] did for everyone
ii new_rest = Forbid[Order[i - 1]][Order[j]].eval(X[Order[i - 1]]);
Rest[Order[j]] = intersect(Rest[Order[j]], new_rest);
}
if(Rest[Order[i]].first > Rest[Order[i]].second) {
ok = false;
break;
}
X[Order[i]] = Rest[Order[i]].second;
}
if(!ok) continue;
for(int i = 0; i < 4; ++i)
ok &= Rest[i].first <= X[i] && X[i] <= Rest[i].second;
if(ok) {
///avem o solutie
vector<ii> Re = {{rh, X[0]}, {X[1], lv}, {lh, X[2]}, {X[3], rv}};
for(auto &[x, y] : Re) {
x = X_posib[x]; y = Y_posib[y];
}
return Re;
}
}
return vector<ii>();
}
vector<ii> sol_k4(vector<steak> S) {
///will return the solution if it satisfies everyone
auto [lh, rh, lv, rv] = get_steak_extremums(S);
vector<ii> Re;
auto check_rest = [&](ii p) {
vector<steak> LeftOver;
for(auto it : S)
if(!it.inside(p)) LeftOver.push_back(it);
auto Cur = sol_k3(LeftOver);
if(!Cur.empty()) {
Cur.push_back(p);
Re = Cur;
}
};
vector<ii> Corners = { {lh, lv}, {lh, rv}, {rh, lv}, {rh, rv}, };
for(auto p : Corners) check_rest(p);
if(!Re.empty())
return Re;
/// now we're sure no corners are used
Re = sol_k4_special(S);
if(!Re.empty()) return Re;
for(auto &it : S) {
it.v.first *= -1; it.v.second *= -1;
swap(it.v.first, it.v.second);
}
Re = sol_k4_special(S);
assert(!Re.empty());
for(auto &[x, y] : Re) y *= -1;
for(auto &it : S) {
it.v.first *= -1; it.v.second *= -1;
swap(it.v.first, it.v.second);
}
for(auto x : S) {
bool ok = false;
for(auto it : Re) {
ok |= x.inside(it);
}
assert(ok);
}
return Re;
}
signed main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int n, k;
cin >> n >> k;
vector<steak> S(n);
for(int i = 0; i < n; ++i) {
cin >> S[i].h.first >> S[i].v.first >> S[i].h.second >> S[i].v.second;
}
vector<ii> Re;
if(k == 1) Re = sol_k1(S);
if(k == 2) Re = sol_k2(S);
if(k == 3) Re = sol_k3(S);
if(k == 4) Re = sol_k4(S);
for(auto it : Re) cout << it.first << " " << it.second << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |