/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 2e5 + 10;
struct event
{
int tim, type, idx;
event(int _tim = 0, int _type = 0, int _idx = 0)
{
tim = _tim;
type = _type;
idx = _idx;
}
bool operator < (const event &e) const
{
if (tim != e.tim)
return tim < e.tim;
return type > e.type;
}
};
struct point
{
int x, y;
point(int _x = 0, int _y = 0)
{
x = _x;
y = _y;
}
void input()
{
cin >> x >> y;
}
void print()
{
cout << x << " " << y << endl;
}
};
struct rectangle
{
point A, B;
rectangle()
{
A = point();
B = point();
}
void input()
{
A.input();
B.input();
}
} r[maxn];
int n, k;
void input()
{
cin >> n >> k;
for (int i = 1; i <= n; i ++)
r[i].input();
}
vector < int > pos_x, pos_y;
const int maxk = 5;
const int maxs = maxk * maxk;
pair < int, int > skew[maxs];
int m;
bitset < maxn > skew_set[maxs];
bool inside(pair < int, int > cur, rectangle rec)
{
if (cur.first >= rec.A.x && cur.first <= rec.B.x &&
cur.second >= rec.A.y && cur.second <= rec.B.y)
return true;
return false;
}
void match_pairs()
{
///cout << pos_x.size() << " : " << pos_y.size() << endl;
for (int x : pos_x)
for (int y : pos_y)
skew[++ m] = {x, y};
for (int i = 1; i <= m; i ++)
for (int j = 1; j <= n; j ++)
skew_set[i][j] = inside(skew[i], r[j]);
}
void find_skewers()
{
if (k == 1)
{
assert(m == 1);
cout << skew[1].first << " " << skew[1].second << endl;
return;
}
if (k == 2)
{
///cout << pos_x.size() << " : " << pos_y.size() << endl;
for (int i = 1; i <= m; i ++)
for (int j = i; j <= m; j ++)
{
if ((skew_set[i] | skew_set[j]).count() == n)
{
cout << skew[i].first << " " << skew[i].second << endl;
cout << skew[j].first << " " << skew[j].second << endl;
return;
}
}
///assert(false);
}
if (k == 3)
{
for (int i = 1; i <= m; i ++)
{
pair < int, int > cur = skew[i];
//cout << cur.first << " " << cur.second << endl;
}
bitset < maxn > temp;
for (int i = 1; i < m; i ++)
{
for (int j = i; j <= m; j ++)
for (int f = j; f <= m; f ++)
{
temp = (skew_set[i] | skew_set[j]);
temp = (temp | skew_set[f]);
///cout << temp.count() << " " << n << " " << n - temp.count() << endl;
if (temp.count() == n)
{
cout << skew[i].first << " " << skew[i].second << endl;
cout << skew[j].first << " " << skew[j].second << endl;
cout << skew[f].first << " " << skew[f].second << endl;
return;
}
}
}
}
}
void solve1()
{
int min_x = 1e9, max_x = 1, min_y = 1e9, max_y = 1;
for (int i = 1; i <= n; i ++)
{
min_x = min(min_x, r[i].B.x);
max_x = max(max_x, r[i].A.x);
min_y = min(min_y, r[i].B.y);
max_y = max(max_y, r[i].A.y);
}
cout << min_x << " " << min_y << endl;
}
int used[maxn];
pair < point, point > solve2()
{
int min_x = 1e9, max_x = 1, min_y = 1e9, max_y = 1;
for (int i = 1; i <= n; i ++)
{
if (used[i])
continue;
min_x = min(min_x, r[i].B.x);
max_x = max(max_x, r[i].A.x);
min_y = min(min_y, r[i].B.y);
max_y = max(max_y, r[i].A.y);
}
if (min_x > max_x && min_y > max_y)
{
return {point(max_x, max_y), point(max_x, max_y)};
}
vector < point > cell;
cell.push_back(point(min_x, min_y));
cell.push_back(point(min_x, max_y));
cell.push_back(point(max_x, min_y));
cell.push_back(point(max_x, max_y));
///cout << min_x << " " << max_x << " " << min_y << " " << max_y << endl;
for (point d : cell)
for (point f : cell)
{
bool done = true;
for (int i = 1; i <= n; i ++)
{
if (used[i])
continue;
if (!inside({d.x, d.y}, r[i]) && !inside({f.x, f.y}, r[i]))
{
done = false;
break;
}
}
if (done)
{
return {d, f};
/**cout << d.x << " " << d.y << endl;
cout << f.x << " " << f.y << endl;
return;*/
}
}
return {point(-1, -1), point(-1, -1)};
}
struct sol3
{
point A, B, C;
sol3(point _A, point _B, point _C)
{
A = _A;
B = _B;
C = _C;
}
};
sol3 solve3()
{
int min_x = 1e9, max_x = 1, min_y = 1e9, max_y = 1;
for (int i = 1; i <= n; i ++)
{
if (used[i])
continue;
min_x = min(min_x, r[i].B.x);
max_x = max(max_x, r[i].A.x);
min_y = min(min_y, r[i].B.y);
max_y = max(max_y, r[i].A.y);
}
vector < point > cell;
cell.push_back(point(min_x, min_y));
cell.push_back(point(min_x, max_y));
cell.push_back(point(max_x, min_y));
cell.push_back(point(max_x, max_y));
for (point cur : cell)
{
for (int i = 1; i <= n; i ++)
{
if (used[i])
continue;
if (inside({cur.x, cur.y}, r[i]))
used[i] = 2;
}
pair < point, point > ans = solve2();
for (int i = 1; i <= n; i ++)
{
if (used[i] == 2)
used[i] = 0;
}
if (ans.first.x == -1)
continue;
return sol3(cur, ans.first, ans.second);
/**cout << cur.x << " " << cur.y << endl;
cout << ans.first.x << " " << ans.first.y << endl;
cout << ans.second.x << " " << ans.second.y << endl;
return;*/
}
return sol3(point(-1, -1), point(-1, -1), point(-1, -1));
}
void solve4()
{
int min_x = 1e9, max_x = 1, min_y = 1e9, max_y = 1;
for (int i = 1; i <= n; i ++)
{
min_x = min(min_x, r[i].B.x);
max_x = max(max_x, r[i].A.x);
min_y = min(min_y, r[i].B.y);
max_y = max(max_y, r[i].A.y);
}
vector < point > cell;
cell.push_back(point(min_x, min_y));
cell.push_back(point(min_x, max_y));
cell.push_back(point(max_x, min_y));
cell.push_back(point(max_x, max_y));
}
void solve()
{
input();
if (k == 1)
solve1();
if (k == 2)
{
pair < point, point > ans = solve2();
cout << ans.first.x << " " << ans.first.y << endl;
cout << ans.second.x << " " << ans.second.y << endl;
}
if (k == 3)
{
sol3 res = solve3();
res.A.print();
res.B.print();
res.C.print();
}
if (k == 4)
{
solve4();
}
}
int main()
{
///freopen("test.txt", "r", stdin);
solve();
return 0;
}
/**
634025969 413050209
458184763 724583533
351907664 172518940
*/
Compilation message
hamburg.cpp: In function 'void find_skewers()':
hamburg.cpp:133:57: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
133 | if ((skew_set[i] | skew_set[j]).count() == n)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
hamburg.cpp:148:31: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
148 | pair < int, int > cur = skew[i];
| ^~~
hamburg.cpp:161:38: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
161 | if (temp.count() == n)
| ~~~~~~~~~~~~~^~~~
hamburg.cpp: In function 'sol3 solve3()':
hamburg.cpp:288:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
288 | if (ans.first.x == -1)
| ^~
hamburg.cpp:291:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
291 | return sol3(cur, ans.first, ans.second);
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4792 KB |
Output is correct |
| 3 |
Correct |
4 ms |
4700 KB |
Output is correct |
| 4 |
Correct |
5 ms |
4796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4700 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4696 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4696 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4696 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4696 KB |
Output is correct |
| 4 |
Correct |
5 ms |
4696 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4700 KB |
Output is correct |
| 6 |
Correct |
4 ms |
4696 KB |
Output is correct |
| 7 |
Correct |
5 ms |
4700 KB |
Output is correct |
| 8 |
Correct |
4 ms |
4796 KB |
Output is correct |
| 9 |
Correct |
4 ms |
4700 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4700 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4700 KB |
Output is correct |
| 12 |
Correct |
4 ms |
4796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4700 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4792 KB |
Output is correct |
| 3 |
Correct |
4 ms |
4700 KB |
Output is correct |
| 4 |
Correct |
5 ms |
4796 KB |
Output is correct |
| 5 |
Correct |
219 ms |
4700 KB |
Output is correct |
| 6 |
Correct |
228 ms |
4700 KB |
Output is correct |
| 7 |
Correct |
270 ms |
4700 KB |
Output is correct |
| 8 |
Correct |
223 ms |
4700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4700 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4696 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4696 KB |
Output is correct |
| 5 |
Correct |
226 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
230 ms |
4764 KB |
Output is correct |
| 7 |
Correct |
229 ms |
4768 KB |
Output is correct |
| 8 |
Correct |
225 ms |
4700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4696 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4696 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4696 KB |
Output is correct |
| 4 |
Correct |
5 ms |
4696 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4700 KB |
Output is correct |
| 6 |
Correct |
4 ms |
4696 KB |
Output is correct |
| 7 |
Correct |
5 ms |
4700 KB |
Output is correct |
| 8 |
Correct |
4 ms |
4796 KB |
Output is correct |
| 9 |
Correct |
4 ms |
4700 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4700 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4700 KB |
Output is correct |
| 12 |
Correct |
4 ms |
4796 KB |
Output is correct |
| 13 |
Correct |
253 ms |
4948 KB |
Output is correct |
| 14 |
Correct |
225 ms |
4764 KB |
Output is correct |
| 15 |
Correct |
235 ms |
4948 KB |
Output is correct |
| 16 |
Correct |
228 ms |
4772 KB |
Output is correct |
| 17 |
Correct |
227 ms |
4768 KB |
Output is correct |
| 18 |
Correct |
230 ms |
4944 KB |
Output is correct |
| 19 |
Correct |
238 ms |
4768 KB |
Output is correct |
| 20 |
Correct |
235 ms |
4772 KB |
Output is correct |
| 21 |
Correct |
232 ms |
4944 KB |
Output is correct |
| 22 |
Correct |
255 ms |
4768 KB |
Output is correct |
| 23 |
Correct |
231 ms |
4768 KB |
Output is correct |
| 24 |
Correct |
266 ms |
4768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4700 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
