#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <random>
#include <chrono>
#include <stack>
#include <queue>
typedef long long llong;
const int MAXN = 200000 + 10;
const int INF = 1e9;
struct Point
{
int x, y;
};
struct Rectangle
{
Point down, up;
bool intersectWith(Rectangle b)
{
if (std::max(down.x, b.down.x) > std::min(up.x, b.up.x)) return false;
if (std::max(down.y, b.down.y) > std::min(up.y, b.up.y)) return false;
return true;
}
Rectangle intersectionWith(Rectangle b)
{
Rectangle result;
result.down.x = std::max(down.x, b.down.x);
result.down.y = std::max(down.y, b.down.y);
result.up.x = std::min(up.x, b.up.x);
result.up.y = std::min(up.y, b.up.y);
return result;
}
};
int n, k;
Rectangle rects[MAXN];
std::vector <Point> solution;
std::vector <Rectangle> rec(std::vector <Rectangle> &curr)
{
if (curr.size() == 1)
{
return curr;
}
std::vector <std::vector <Rectangle>> split;
for (const Rectangle &currRect : curr)
{
bool found = false;
for (int i = 0 ; i < split.size() ; ++i)
{
if (split[i][0].intersectWith(currRect))
{
found = true;
split[i].push_back(currRect);
}
}
if (!found)
{
split.push_back({currRect});
continue;
}
}
if (split.size() == 1)
{
Rectangle begin = split[0][0];
split[0].erase(split[0].begin());
std::vector <Rectangle> sol = rec(split[0]);
for (int i = 0 ; i < sol.size() ; ++i)
{
assert(sol[i].intersectWith(begin));
sol[i] = sol[i].intersectionWith(begin);
}
return sol;
}
std::vector <Rectangle> sol;
for (std::vector <Rectangle> &currSplit : split)
{
std::vector <Rectangle> res = rec(currSplit);
for (const Rectangle &r : res)
{
sol.push_back(r);
}
}
return sol;
}
std::mt19937 rng(69420); //std::chrono::steady_clock::now().time_since_epoch().count());
void solve()
{
std::vector <Rectangle> solveFor;
for (int i = 1 ; i <= n ; ++i)
{
solveFor.push_back(rects[i]);
}
std::shuffle(solveFor.begin(), solveFor.end(), rng);
std::vector <Rectangle> mySol = rec(solveFor);
for (int i = 0 ; i < mySol.size() ; ++i)
{
solution.push_back(mySol[i].down);
}
assert(solution.size() <= k);
while (solution.size() < k) solution.push_back(solution.back());
for (const Point &curr : solution)
{
std::cout << curr.x << ' ' << curr.y << '\n';
}
}
void input()
{
std::cin >> n >> k;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> rects[i].down.x >> rects[i].down.y >> rects[i].up.x >> rects[i].up.y;
if (rects[i].down.x > rects[i].up.x) std::swap(rects[i].down.x, rects[i].up.x);
if (rects[i].down.y > rects[i].up.y) std::swap(rects[i].down.y, rects[i].up.y);
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
Compilation message
hamburg.cpp: In function 'std::vector<Rectangle> rec(std::vector<Rectangle>&)':
hamburg.cpp:56:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<Rectangle> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i = 0 ; i < split.size() ; ++i)
| ~~^~~~~~~~~~~~~~
hamburg.cpp:78:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Rectangle>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for (int i = 0 ; i < sol.size() ; ++i)
| ~~^~~~~~~~~~~~
hamburg.cpp: In function 'void solve()':
hamburg.cpp:112:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Rectangle>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for (int i = 0 ; i < mySol.size() ; ++i)
| ~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from hamburg.cpp:4:
hamburg.cpp:117:28: warning: comparison of integer expressions of different signedness: 'std::vector<Point>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
117 | assert(solution.size() <= k);
| ~~~~~~~~~~~~~~~~^~~~
hamburg.cpp:118:28: warning: comparison of integer expressions of different signedness: 'std::vector<Point>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
118 | while (solution.size() < k) solution.push_back(solution.back());
| ~~~~~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
37460 KB |
Output is correct |
| 2 |
Correct |
24 ms |
37212 KB |
Output is correct |
| 3 |
Correct |
24 ms |
37472 KB |
Output is correct |
| 4 |
Correct |
24 ms |
37724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
409 ms |
69292 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
218 ms |
34268 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
223 ms |
58960 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
37460 KB |
Output is correct |
| 2 |
Correct |
24 ms |
37212 KB |
Output is correct |
| 3 |
Correct |
24 ms |
37472 KB |
Output is correct |
| 4 |
Correct |
24 ms |
37724 KB |
Output is correct |
| 5 |
Runtime error |
906 ms |
1048576 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
409 ms |
69292 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
218 ms |
34268 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
223 ms |
58960 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
