#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
const int MAXN = 100013;
const int INF = 1e9 + 7;
const long long LLINF = 3e18;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int N, K;
vpl arr;
ll mnx = LLINF, mxx = -LLINF, mny = LLINF, mxy = -LLINF;
pair<pll, pll> calc(vpl v)
{
ll lox = LLINF, hix = -LLINF, loy = LLINF, hiy = -LLINF;
for (pll p : v)
{
ckmin(lox, p.fi);
ckmax(hix, p.fi);
ckmin(loy, p.se);
ckmax(hiy, p.se);
}
return {{lox, hix}, {loy, hiy}};
}
pair<pll, pll> ok(ll c)
{
//try smth containing top left.
// cerr << "CHECKING " << c << endl;
pair<pll, pll> res, box;
vpl pts;
FOR(i, 0, N)
{
if (arr[i].fi <= mnx + c && arr[i].se <= mny + c)
{
continue;
}
pts.PB(arr[i]);
}
// for (pll p : pts)
// {
// cerr << p.fi << ' ' << p.se << endl;
// }
box = calc(pts);
// cerr << box.fi.fi << ' ' << box.se.fi << ' ' << mnx + c << ' ' << mny + c << ' ' << max(box.fi.se - box.fi.fi, box.se.se - box.se.fi) << endl;
if ((box.fi.fi > mnx + c || box.se.fi > mny + c) && max(box.fi.se - box.fi.fi, box.se.se - box.se.fi) <= c)
{
// cerr << "SHOULD WORK\n";
return {{mnx, mny}, {box.fi.fi, box.se.fi}};
}
pts.clear();
FOR(i, 0, N)
{
if (arr[i].fi >= mxx - c && arr[i].se <= mny + c)
{
continue;
}
pts.PB(arr[i]);
}
box = calc(pts);
if ((box.fi.se < mxx - c || box.se.fi > mny + c) && max(box.fi.se - box.fi.fi, box.se.se - box.se.fi) <= c)
{
return {{mxx - c, mny}, {box.fi.se - c, box.se.fi}};
}
pts.clear();
FOR(i, 0, N)
{
if (arr[i].fi <= mnx + c && arr[i].se >= mxy - c)
{
continue;
}
pts.PB(arr[i]);
}
box = calc(pts);
if ((box.fi.fi > mnx + c || box.se.se < mny - c) && max(box.fi.se - box.fi.fi, box.se.se - box.se.fi) <= c)
{
return {{mnx, mxy - c}, {box.fi.fi, box.se.se - c}};
}
pts.clear();
FOR(i, 0, N)
{
if (arr[i].fi >= mxx - c && arr[i].se >= mxy - c)
{
continue;
}
pts.PB(arr[i]);
}
box = calc(pts);
if ((box.fi.se < mxx - c || box.se.se < mny - c) && max(box.fi.se - box.fi.fi, box.se.se - box.se.fi) <= c)
{
return {{mxx - c, mxy - c}, {box.fi.se - c, box.se.se - c}};
}
// cerr << "FAILED " << c << endl;
return {{LLINF, LLINF}, {LLINF, LLINF}};
}
int32_t main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(12);
cerr << fixed << setprecision(4);
cin >> N >> K;
arr.resize(N);
FOR(i, 0, N)
{
cin >> arr[i].fi >> arr[i].se;
}
auto e = calc(arr);
mnx = e.fi.fi; mxx = e.fi.se;
mny = e.se.fi; mxy = e.se.se;
if (K == 1)
{
cout << mnx << ' ' << mny << ' ' << max(1ll, max(mxx - mnx, mxy - mny)) << '\n';
return 0;
}
if (K == 2)
{
ll lo = 1, hi = max(mxx - mnx, mxy - mny);
while(hi > lo)
{
ll mid = (hi + lo) >> 1;
auto e = ok(mid);
if (e.fi == MP(LLINF, LLINF)) lo = mid + 1;
else hi = mid;
}
auto e = ok(lo);
if (e.se.fi >= 10ll * INF)
{
e.se = {e.fi.fi + lo + 1, e.fi.se + lo + 1};
}
cout << e.fi.fi << ' ' << e.fi.se << ' ' << lo << '\n';
cout << e.se.fi << ' ' << e.se.se << ' ' << lo << '\n';
// assert(abs(e.fi.fi - e.se.fi) > lo || abs(e.fi.se - e.se.se) > lo);
FOR(i, 0, N)
{
ll x = arr[i].fi, y = arr[i].se;
bool b1 = (e.fi.fi <= x && x <= e.fi.fi + lo) && (e.fi.se <= y && y <= e.fi.se + lo);
bool b2 = (e.se.fi <= x && x <= e.se.fi + lo) && (e.se.se <= y && y <= e.se.se + lo);
assert(b1 || b2);
}
return 0;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
30 ms |
3428 KB |
Output is correct |
| 8 |
Correct |
28 ms |
3396 KB |
Output is correct |
| 9 |
Correct |
28 ms |
3424 KB |
Output is correct |
| 10 |
Correct |
30 ms |
3396 KB |
Output is correct |
| 11 |
Correct |
28 ms |
3404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Incorrect |
54 ms |
5052 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
