#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <assert.h>
#define maxn 2000000
using namespace std;
int low [maxn];
int dfn [maxn];
bool instack [maxn];
stack <int> s;
vector <int> edgs [maxn];
int sccid [maxn];
int t = 0;
int sccct = 0;
int n;
void dfs(int u){
low[u] = ++t;
dfn[u] = t;
s.push(u);
instack[u] = true;
for(int i = 0; i < edgs[u].size(); i++){
if(dfn[edgs[u][i]] == 0){
dfs(edgs[u][i]);
low[u] = min(low[edgs[u][i]], low[u]);
}else if(instack[edgs[u][i]]){
low[u] = min(low[u], dfn[edgs[u][i]]);
}
}
if(low[u] == dfn[u]){
++sccct;
while(!s.empty()){
int x = s.top();
sccid[x] = sccct;
s.pop();
instack[x] = false;
if(x == u){
break;
}
}
}
}
int neg(int x){
if(x <= n){
return x + n;
}else{
return x - n;
}
}
struct rect{
int l, r, d, u;
rect(int lin, int rin, int din, int uin){
l = lin;
r = rin;
d = din;
u = uin;
}
};
struct point{
int x, y;
point(int xin, int yin){
x = xin;
y = yin;
}
};
bool in(point p, rect r){
return (r.l <= p.x && p.x <= r.r && r.d <= p.y && p.y <= r.u);
}
vector <rect> removeSkewered(vector <rect> v, point p){
vector <rect> vv;
for(int i = 0; i < v.size(); i++){
if(!in(p, v[i])){
vv.push_back(v[i]);
}
}
return vv;
}
vector <point> ans;
bool solveCorners(vector <rect> v, int k){
if(k == 0){
if(v.size() != 0){
return false;
}else{
return true;
}
}else{
if(v.size() != 0){
int maxL = 1;
int minR = 1e9;
int maxD = 1;
int minU = 1e9;
for(int i = 0; i < v.size(); i++){
maxL = max(maxL, v[i].l);
minR = min(minR, v[i].r);
maxD = max(maxD, v[i].d);
minU = min(minU, v[i].u);
}
vector <point> testPoints;
if(maxL <= minR){
minR = maxL;
}else{
minU = maxD;
}
int possX [2] = {maxL, minR};
int possY [2] = {maxD, minU};
int itr1 = 2;
int itr2 = 2;
if(possX[0] == possX[1]){
itr1 = 1;
}
if(possY[0] == possY[1]){
itr2 = 1;
}
for(int i = 0; i < itr1; i++){
for(int j = 0; j < itr2; j++){
if(solveCorners(removeSkewered(v, point(possX[i], possY[j])), k-1)){
ans.push_back(point(possX[i], possY[j]));
return true;
}
}
}
return false;
}else{
return true;
}
}
}
bool solveSides(vector <rect> v){
int maxL = 1;
int minR = 1e9;
int maxD = 1;
int minU = 1e9;
for(int i = 0; i < v.size(); i++){
maxL = max(maxL, v[i].l);
minR = min(minR, v[i].r);
maxD = max(maxD, v[i].d);
minU = min(minU, v[i].u);
}
// cout << maxL << " " << minR << " " << maxD << " " << minU << endl;
if(minR+1 < maxL && minU+1 < maxD){
map <pair<int,int>, int> mp;
vector <pair<pair<bool, pair<int,int>>, pair<bool, pair<int,int>>>> edgesList;
for(int i = 0; i < v.size(); i++){
int ll = v[i].l;
int rr = v[i].r;
int dd = v[i].d;
int uu = v[i].u;
// cout << ll << " " << rr << " " << dd << " " << uu << endl;
if((ll <= minR+1 && maxL-1 <= rr) || (dd <= minU+1 && maxD-1 <= uu)){
//full side cases (> 3 sides) : do nothing
}else if(rr < minR || maxL < ll || uu < minU || maxD < dd){
//outside the rectangle: do nothing
}else{
vector <pair<int, pair <int, int>>> inter;
if(ll <= minR && minR <= rr){
if((minU+1) <= dd && dd <= (maxD-1) || (minU+1) <= uu && uu <= (maxD-1)){
inter.push_back(make_pair(1, make_pair(max(minU+1, dd), min(maxD-1, uu))));
}
}
if(ll <= maxL && maxL <= rr){
if((minU+1) <= dd && dd <= (maxD-1) || (minU+1) <= uu && uu <= (maxD-1)){
// cout << minU+1 << " " << dd << "***" << maxD-1 << " " << uu << endl;
inter.push_back(make_pair(2, make_pair(max(minU+1, dd), min(maxD-1, uu))));
}
}
if(dd <= minU && minU <= uu){
// cout << "-" << endl;
if((minR+1) <= ll && ll <= (maxL-1) || (minR+1) <= rr && rr <= (maxL-1)){
inter.push_back(make_pair(3, make_pair(max(minR+1, ll), min(maxL-1, rr))));
}
}
if(dd <= maxD && maxD <= uu){
// cout << "-" << endl;
if((minR+1) <= ll && ll <= (maxL-1) || (minR+1) <= rr && rr <= (maxL-1)){
inter.push_back(make_pair(4, make_pair(max(minR+1, ll), min(maxL-1, rr))));
}
}
if(inter.size() >= 3){
cout << "??? 190" << endl;
return false;
}else if(inter.size() == 0){
//do nothing
}else if(inter.size() == 1){
int side = inter[0].first;
int left = inter[0].second.first-1;
int right = inter[0].second.second;
if(mp.find(make_pair(side,left)) == mp.end()){
mp[make_pair(side, left)] = ++n;
}
if(mp.find(make_pair(side,right)) == mp.end()){
mp[make_pair(side, right)] = ++n;
}
// cout << i << " " << side << " " << inter[0].second.first << "/" << inter[0].second.second << endl;
edgesList.push_back(make_pair(make_pair(true, make_pair(side, left)), make_pair(false, make_pair(side, left))));
edgesList.push_back(make_pair(make_pair(false, make_pair(side, right)), make_pair(true, make_pair(side, right))));
}else{
int side0 = inter[0].first;
int left0 = inter[0].second.first-1;
int right0 = inter[0].second.second;
int side1 = inter[1].first;
int left1 = inter[1].second.first-1;
int right1 = inter[1].second.second;
if(mp.find(make_pair(side0,left0)) == mp.end()){
mp[make_pair(side0, left0)] = ++n;
}
if(mp.find(make_pair(side0,right0)) == mp.end()){
mp[make_pair(side0, right0)] = ++n;
}
if(mp.find(make_pair(side1,left1)) == mp.end()){
mp[make_pair(side1, left1)] = ++n;
}
if(mp.find(make_pair(side1,right1)) == mp.end()){
mp[make_pair(side1, right1)] = ++n;
}
edgesList.push_back(make_pair(make_pair(true, make_pair(side0, left0)), make_pair(false, make_pair(side1, left1))));
edgesList.push_back(make_pair(make_pair(true, make_pair(side1, left1)), make_pair(false, make_pair(side0, left0))));
edgesList.push_back(make_pair(make_pair(false, make_pair(side0, right0)), make_pair(false, make_pair(side1, left1))));
edgesList.push_back(make_pair(make_pair(true, make_pair(side1, left1)), make_pair(true, make_pair(side0, right0))));
edgesList.push_back(make_pair(make_pair(true, make_pair(side0, left0)), make_pair(true, make_pair(side1, right1))));
edgesList.push_back(make_pair(make_pair(false, make_pair(side1, right1)), make_pair(false, make_pair(side0, left0))));
edgesList.push_back(make_pair(make_pair(false, make_pair(side0, right0)), make_pair(true, make_pair(side1, right1))));
edgesList.push_back(make_pair(make_pair(false, make_pair(side1, right1)), make_pair(true, make_pair(side0, right0))));
}
}
}
if(mp.find(make_pair(1, maxD-1)) == mp.end()){
mp[make_pair(1, maxD-1)] = ++n;
}
edgesList.push_back(make_pair(make_pair(false, make_pair(1, maxD-1)), make_pair(true, make_pair(1, maxD-1))));
if(mp.find(make_pair(2, maxD-1)) == mp.end()){
mp[make_pair(2, maxD-1)] = ++n;
}
edgesList.push_back(make_pair(make_pair(false, make_pair(2, maxD-1)), make_pair(true, make_pair(2, maxD-1))));
if(mp.find(make_pair(3, maxL-1)) == mp.end()){
mp[make_pair(3, maxL-1)] = ++n;
}
edgesList.push_back(make_pair(make_pair(false, make_pair(3, maxL-1)), make_pair(true, make_pair(3, maxL-1))));
if(mp.find(make_pair(4, maxL-1)) == mp.end()){
mp[make_pair(4, maxL-1)] = ++n;
}
edgesList.push_back(make_pair(make_pair(false, make_pair(4, maxL-1)), make_pair(true, make_pair(4, maxL-1))));
vector <pair<int,int>> sides [4];
int prevSide = 0;
int prevCord = 0;
for(auto i = mp.begin(); i != mp.end(); i++){
pair<pair <int,int>, int> pii = *i;
// cout << pii.first.first << " " << pii.first.second << " " << pii.second << endl;
sides[pii.first.first-1].push_back(make_pair(pii.first.second, pii.second));
if(pii.first.first == prevSide){
edgesList.push_back(make_pair(make_pair(true, make_pair(prevSide, prevCord)), make_pair(true, pii.first)));
edgesList.push_back(make_pair(make_pair(false, pii.first), make_pair(false, make_pair(prevSide, prevCord))));
}
prevSide = pii.first.first;
prevCord = pii.first.second;
}
// cout << n << endl;
for(int i = 0; i < edgesList.size(); i++){
// cout << edgesList[i].first.first << " " << edgesList[i].first.second.first << " " << edgesList[i].first.second.second;
// cout << " -- ";
// cout << edgesList[i].second.first << " " << edgesList[i].second.second.first << " " << edgesList[i].second.second.second;
// cout << endl;
pair<bool,pair<int,int>> v1 = edgesList[i].first;
pair<bool,pair<int,int>> v2 = edgesList[i].second;
int v1id = mp[v1.second];
if(!v1.first){
v1id = neg(v1id);
}
int v2id = mp[v2.second];
if(!v2.first){
v2id = neg(v2id);
}
edgs[v1id].push_back(v2id);
}
for(int i = 1; i <= 2*n; i++){
if(dfn[i] == 0){
dfs(i);
}
}
bool pos = true;
for(int i = 1; i <= n; i++){
// cout << sccid[i] << " " << sccid[i+n] << endl;
if(sccid[i] == sccid[i+n]){
pos = false;
}
}
if(!pos){
// cout << "***" << endl;
return false;
}
for(int i = 0; i < 4; i++){
for(int j = 0; j < sides[i].size(); j++){
if(sccid[sides[i][j].second] < sccid[sides[i][j].second+n]){
if(i == 0){
ans.push_back(point(minR, sides[i][j].first));
}else if(i == 1){
ans.push_back(point(maxL, sides[i][j].first));
}else if(i == 2){
ans.push_back(point(sides[i][j].first, minU));
}else{
ans.push_back(point(sides[i][j].first, maxD));
}
break;
}
}
// cout << endl;
}
if(ans.size() != 4){
assert(0);
cout << "??? 319" << endl;
return false;
}else{
return true;
}
}else{
return false;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, K;
cin >> N >> K;
vector <rect> rectArr;
for(int i = 0; i < N; i++){
int ll, rr, dd, uu;
cin >> ll >> dd >> rr >> uu;
rectArr.push_back(rect(ll, rr, dd, uu));
}
if(solveCorners(rectArr,K)){
for(int i = 0; i < ans.size(); i++){
cout << ans[i].x << " " << ans[i].y << endl;
}
}else if(K == 4 && solveSides(rectArr)){
for(int i = 0; i < ans.size(); i++){
cout << ans[i].x << " " << ans[i].y << endl;
}
}else{
cout << "I GIVE UP GOODBYE" << endl;
}
}
Compilation message
hamburg.cpp: In function 'void dfs(int)':
hamburg.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 0; i < edgs[u].size(); i++){
| ~~^~~~~~~~~~~~~~~~
hamburg.cpp: In function 'std::vector<rect> removeSkewered(std::vector<rect>, point)':
hamburg.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
hamburg.cpp: In function 'bool solveCorners(std::vector<rect>, int)':
hamburg.cpp:120:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
hamburg.cpp: In function 'bool solveSides(std::vector<rect>)':
hamburg.cpp:162:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
hamburg.cpp:172:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
hamburg.cpp:185:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
185 | if((minU+1) <= dd && dd <= (maxD-1) || (minU+1) <= uu && uu <= (maxD-1)){
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
hamburg.cpp:190:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
190 | if((minU+1) <= dd && dd <= (maxD-1) || (minU+1) <= uu && uu <= (maxD-1)){
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
hamburg.cpp:197:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
197 | if((minR+1) <= ll && ll <= (maxL-1) || (minR+1) <= rr && rr <= (maxL-1)){
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
hamburg.cpp:203:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
203 | if((minR+1) <= ll && ll <= (maxL-1) || (minR+1) <= rr && rr <= (maxL-1)){
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
hamburg.cpp:296:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<bool, std::pair<int, int> >, std::pair<bool, std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
296 | for(int i = 0; i < edgesList.size(); i++){
| ~~^~~~~~~~~~~~~~~~~~
hamburg.cpp:330:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
330 | for(int j = 0; j < sides[i].size(); j++){
| ~~^~~~~~~~~~~~~~~~~
hamburg.cpp: In function 'int main()':
hamburg.cpp:370:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
370 | for(int i = 0; i < ans.size(); i++){
| ~~^~~~~~~~~~~~
hamburg.cpp:374:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
374 | for(int i = 0; i < ans.size(); i++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
47444 KB |
Output is correct |
| 2 |
Correct |
24 ms |
47440 KB |
Output is correct |
| 3 |
Correct |
23 ms |
47400 KB |
Output is correct |
| 4 |
Correct |
24 ms |
47480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
47428 KB |
Output is correct |
| 2 |
Correct |
25 ms |
47504 KB |
Output is correct |
| 3 |
Correct |
27 ms |
47368 KB |
Output is correct |
| 4 |
Correct |
26 ms |
47548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
47520 KB |
Output is correct |
| 2 |
Correct |
26 ms |
47444 KB |
Output is correct |
| 3 |
Correct |
26 ms |
47512 KB |
Output is correct |
| 4 |
Correct |
25 ms |
47452 KB |
Output is correct |
| 5 |
Correct |
24 ms |
47476 KB |
Output is correct |
| 6 |
Correct |
27 ms |
47432 KB |
Output is correct |
| 7 |
Correct |
25 ms |
47452 KB |
Output is correct |
| 8 |
Incorrect |
26 ms |
47572 KB |
Expected integer, but "I" found |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
47404 KB |
Output is correct |
| 2 |
Correct |
29 ms |
47488 KB |
Output is correct |
| 3 |
Correct |
25 ms |
47404 KB |
Output is correct |
| 4 |
Correct |
25 ms |
47444 KB |
Output is correct |
| 5 |
Correct |
26 ms |
47528 KB |
Output is correct |
| 6 |
Correct |
25 ms |
47528 KB |
Output is correct |
| 7 |
Correct |
25 ms |
47432 KB |
Output is correct |
| 8 |
Incorrect |
28 ms |
48032 KB |
Expected integer, but "I" found |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
47444 KB |
Output is correct |
| 2 |
Correct |
24 ms |
47440 KB |
Output is correct |
| 3 |
Correct |
23 ms |
47400 KB |
Output is correct |
| 4 |
Correct |
24 ms |
47480 KB |
Output is correct |
| 5 |
Correct |
109 ms |
64120 KB |
Output is correct |
| 6 |
Correct |
116 ms |
64232 KB |
Output is correct |
| 7 |
Correct |
110 ms |
64164 KB |
Output is correct |
| 8 |
Correct |
107 ms |
64252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
47428 KB |
Output is correct |
| 2 |
Correct |
25 ms |
47504 KB |
Output is correct |
| 3 |
Correct |
27 ms |
47368 KB |
Output is correct |
| 4 |
Correct |
26 ms |
47548 KB |
Output is correct |
| 5 |
Correct |
114 ms |
67652 KB |
Output is correct |
| 6 |
Correct |
117 ms |
71416 KB |
Output is correct |
| 7 |
Correct |
115 ms |
67488 KB |
Output is correct |
| 8 |
Correct |
127 ms |
75004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
47520 KB |
Output is correct |
| 2 |
Correct |
26 ms |
47444 KB |
Output is correct |
| 3 |
Correct |
26 ms |
47512 KB |
Output is correct |
| 4 |
Correct |
25 ms |
47452 KB |
Output is correct |
| 5 |
Correct |
24 ms |
47476 KB |
Output is correct |
| 6 |
Correct |
27 ms |
47432 KB |
Output is correct |
| 7 |
Correct |
25 ms |
47452 KB |
Output is correct |
| 8 |
Incorrect |
26 ms |
47572 KB |
Expected integer, but "I" found |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
47404 KB |
Output is correct |
| 2 |
Correct |
29 ms |
47488 KB |
Output is correct |
| 3 |
Correct |
25 ms |
47404 KB |
Output is correct |
| 4 |
Correct |
25 ms |
47444 KB |
Output is correct |
| 5 |
Correct |
26 ms |
47528 KB |
Output is correct |
| 6 |
Correct |
25 ms |
47528 KB |
Output is correct |
| 7 |
Correct |
25 ms |
47432 KB |
Output is correct |
| 8 |
Incorrect |
28 ms |
48032 KB |
Expected integer, but "I" found |
| 9 |
Halted |
0 ms |
0 KB |
- |
