#include<iostream>
#include<algorithm>
#include<deque>
#include<cassert>
using namespace std;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
struct pt{
int x, y, ind;
pt(int X, int Y, int I){
x=X, y=Y, ind=I;
}
pt(){}
};
struct rect{
int assi;
ll l, d, r, u;
rect(ll L, ll D, ll R, ll U, int A=2000000000){
l=L, d=D, r=R, u=U, assi=A;
}
rect(){l=d=r=u=0, assi=-1;}
void transform(bool a, bool b, bool c){
int aux;
if(a) aux=l, l=-r, r=-aux;
if(b) aux=d, d=-u, u=-aux;
if(c) swap(l, d), swap(r, u);
}
};
struct sol{
bool valid;
rect re[3];
sol(){
valid = false;
}
sol(rect R1, rect R2, rect R3){
re[0]=R1, re[1]=R2, re[2]=R3, valid=true;
}
void print(){forn(i, 3) if(re[i].assi!=-1) assert(re[i].u>=re[i].d), cout << re[i].l << ' ' << re[i].d << ' ' << re[i].u-re[i].d << '\n';}
void dummySquare(int num){
int start = 2001000000;
forn(i, 3){
num+=(re[i].assi==-1);
if(re[i].assi==-1 && num>3) re[i]=rect(start, 0, start+1, 1, 0), start+=2;
}
}
void transform(bool a, bool b, bool c){
forn(i, 3) re[i].transform(a, b, c);
}
};
const int MAXN=100010, INF=2000000100;
int n, k, ext[MAXN], calc[MAXN];
ll st[2*MAXN], st1[MAXN], st2[MAXN];
bool seen[MAXN];
pt srt[2][2][2][MAXN], varg[MAXN];
rect le[2][2][2], oneans;
auto fstCmp = [](pt a, pt b){
return a.x<b.x;
};
auto sndCmp = [](pt a, pt b){
return a.y<b.y;
};
rect cover(pt* arr, int m){
int mn=INF, mx=-INF;
forn(i, m) mn=min(mn, arr[i].y), mx=max(mx, arr[i].y);
return rect(arr[0].x, mn, arr[m-1].x, mx);
}
rect push_corner(rect re, int dir, int len){
switch(dir){
case 0: return rect(re.l, re.d, re.l+len, re.d+len);
case 1: return rect(re.r-len, re.d, re.r, re.d+len);
case 2: return rect(re.l, re.u-len, re.l+len, re.u);
case 3: return rect(re.r-len, re.u-len, re.r, re.u);
}
}
rect rightmost(pt* arr, int m, int side){
int mn=INF, mx=-INF; rect ret;
forn(i, m){
mx=max(mx, arr[i].y), mn=min(mn, arr[i].y);
if(arr[i].x-arr[0].x>side || mx-mn>side) break;
if(i==m-1 || arr[i+1].x!=arr[i].x) ret = rect(arr[0].x, mn, arr[i].x, mx, i);
}
return ret;
}
sol low_high_check(pt* arr, int l, int r, int side){
int high_left = max_element(arr, arr+l, sndCmp)->y;
int high_center = max_element(arr+l, arr+r, sndCmp)->y;
int low_center = min_element(arr+l, arr+r, sndCmp)->y;
int low_right = min_element(arr+r, arr+n, sndCmp)->y;
if(high_left>high_center || low_center>low_right) return sol();
ext[l]=low_center, ext[r-1]=high_center;
dforn(i, l) ext[i]=min(ext[i+1], arr[i].y);
forsn(i, r, n) ext[i]=max(ext[i-1], arr[i].y);
dforn(i, l) calc[i]=ext[i+1]-arr[i].x;
forsn(i, r, n) calc[i]=ext[i-1]-arr[i].x;
dforn(i, l-1) calc[i]=max(calc[i+1], calc[i]);
forsn(i, r+1, n) calc[i]=min(calc[i-1], calc[i]);
int pos=r;
forn(i, l){
while(pos<n && (calc[pos]+2>calc[i] || (ext[pos-1]==ext[i+1] && arr[pos].x-arr[i].x==2))) ++pos;
int width = arr[pos].x - arr[i].x - 2, height = max(ext[pos-1]-ext[i+1], 1);
if(height<=width && height<=side){
ll left_edge = max(arr[i].x+1, arr[r-1].x-height);
int szl = lower_bound(arr, arr+n, pt(left_edge, -INF, 0), fstCmp)-arr;
int szr = upper_bound(arr, arr+n, pt(left_edge+height, INF, 0), fstCmp)-arr;
return sol(push_corner(cover(arr, szl), 1, side),
push_corner(cover(arr+szr, n-szr), 0, side),
rect(left_edge, ext[i+1], left_edge+height, ext[pos-1]));
}
}
return sol();
}
sol lowest_check(pt* arr, pt* brr, int l, int r, int side){
if(arr[r-1].x - arr[l].x > side) return sol();
int pos = find_if(arr, arr+n, [&brr](pt a){
return a.ind==brr[0].ind;
}) - arr;
if(pos<l || pos>=r) return sol();
int L=pos, R=pos;
forn(i, n) seen[i]=false;
forn(i, n){
seen[brr[i].ind]=true;
while(L>0 && seen[arr[L-1].ind]) --L;
while(R<n-1 && seen[arr[R+1].ind]) ++R;
int height=max(brr[i].x-brr[0].x, 1);
if(L<=l && R>=r-1 && height<=side && (L==0 || R==n-1 || (height<=arr[R+1].x-arr[L-1].x-2))){
ll left_edge = max(L==0? -INF : arr[L-1].x+1, arr[r-1].x-height);
int szl = lower_bound(arr, arr+n, pt(left_edge, -INF, 0), fstCmp)-arr;
int szr = upper_bound(arr, arr+n, pt(left_edge+height, INF, 0), fstCmp)-arr;
return sol(push_corner(cover(arr, szl), 1, side),
push_corner(cover(arr+szr, n-szr), 0, side),
rect(left_edge, brr[0].x, left_edge+height, brr[i].x));
}
}
return sol();
}
sol equal_check(pt* arr, int l, int r, int side){
int L=0, R=0;
deque<int> mn, mx;
forn(i, n) st1[i]=arr[i].x+1, st2[i]=arr[i].x-(ll)side;
merge(st1, st1+n, st2, st2+n, st);
mn.push_back(arr[0].y);
mx.push_back(arr[0].y);
forn(i, 2*n){
while(R<n && arr[R+1].x<=st[i]+side){
++R;
while(!mn.empty() && mn.back()>arr[R].y) mn.pop_back();
while(!mx.empty() && mx.back()<arr[R].y) mx.pop_back();
mx.push_back(arr[R].y);
mn.push_back(arr[R].y);
}
while(L<n && arr[L].x<st[i]){
if(!mn.empty() && arr[L].y==mn.front()) mn.pop_front();
if(!mx.empty() && arr[L].y==mx.front()) mx.pop_front();
++L;
}
if(L<=l && R>=r-1 && mx.front()-mn.front()<=side){
ll left_edge = max(arr[L-1].x+1, arr[r-1].x-side);
return sol(push_corner(cover(arr, L), 1, side),
push_corner(cover(arr+R+1, n-R-1), 0, side),
rect(left_edge, mn.front(), left_edge+side, mn.front()+side));
}
}
return sol();
}
sol check_two(pt* arr, int m, int side){
rect fst=rightmost(arr, m, side);
rect snd=rightmost(arr+fst.assi+1, m-fst.assi-1, side);
if((fst.assi==-1 || snd.assi==-1) && fst.assi!=m-1 && snd.assi!=m-1) return sol();
if(fst.assi+snd.assi+2==m) return sol(rect(), fst, snd);
return sol();
}
sol v2_check(pt* arr, pt* brr, int side){
int m=0;
rect fst=rightmost(arr, n, side);
forn(i, n) seen[i]=false;
forn(i, fst.assi+1) seen[arr[i].ind]=true;
forn(i, n) if(!seen[brr[i].ind]) varg[m++]=brr[i];
sol ret = check_two(varg, m, side);
if(m!=0 && !ret.valid) return sol();
ret.transform(0, 0, 1);
ret.re[0]=push_corner(fst, 1, side);
ret.re[1]=push_corner(ret.re[1], 2, side);
ret.re[2]=push_corner(ret.re[2], 0, side);
return ret;
}
sol horizontal_checks(int side){
forn(i, 2){
sol ret = equal_check(srt[0][0][i], le[0][0][i].assi+1, n-le[1][0][i].assi-1, side);
if(ret.valid){
ret.transform(0, 0, i);
return ret;
}
}
forn(i, 2) forn(j, 2){
sol ret = lowest_check(srt[0][i][j], srt[i][0][j^1], le[0][i][j].assi+1, n-le[1][i][j].assi-1, side);
if(ret.valid){
ret.transform(0, i, j);
return ret;
}
ret = low_high_check(srt[0][i][j], le[0][i][j].assi+1, n-le[1][i][j].assi-1, side);
if(ret.valid){
ret.transform(0, i, j);
return ret;
}
}
return sol();
}
sol cross_checks(int side){
forn(i, 2) forn(j, 2){
sol ret = v2_check(srt[i][0][j], srt[0][i][j^1], side);
if(ret.valid){
ret.transform(i, 0, j);
return ret;
}
}
return sol();
}
sol test(int type, int side){
if(side>=oneans.r-oneans.l) return sol(rect(), rect(), oneans);
forn(i, 2) forn(j, 2) forn(w, 2) le[i][j][w] = rightmost(srt[i][j][w], n, side);
forn(i, 2) if(le[0][0][i].assi+le[1][0][i].assi>=n-2){
sol ret = check_two(srt[0][0][i], n, side);
ret.re[1]=push_corner(ret.re[1], 1, side);
ret.re[2]=push_corner(ret.re[2], 0, side);
ret.transform(0, 0, i);
return ret;
}
if(type==2) return sol();
sol ret = horizontal_checks(side);
if(ret.valid) return ret;
ret = cross_checks(side);
if(ret.valid) return ret;
return sol();
}
int main(){
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> k;
forn(i, n){
int a, b; cin >> a >> b;
srt[0][0][0][i] = pt(a, b, i);
srt[0][0][1][i] = pt(b, a, i);
}
forn(i, 2) sort(srt[0][0][i], srt[0][0][i]+n, fstCmp);
forn(i, 2) forn(j, n) srt[0][1][i][j]=pt(srt[0][0][i][j].x, -srt[0][0][i][j].y, srt[0][0][i][j].ind);
forn(i, 2) forn(j, 2) forn(w, n) srt[1][i][j][w]=pt(-srt[0][i][j][n-1-w].x, srt[0][i][j][n-1-w].y, srt[0][i][j][n-1-w].ind);
oneans = cover(srt[0][0][0], n);
oneans = push_corner(oneans, 0, max(max(oneans.r-oneans.l, oneans.u-oneans.d), 1LL));
if(k==1){
sol(rect(), rect(), oneans).print();
return 0;
}
int lo=0, hi=INF;
sol ans;
while(hi-lo>1){
int mid = ((hi-lo)>>1)+lo;
sol partial = test(k, mid);
if(partial.valid) hi=mid, ans=partial;
else lo=mid;
}
ans.dummySquare(k);
ans.print();
}
Compilation message
izvanzemaljci.cpp: In function 'rect push_corner(rect, int, int)':
izvanzemaljci.cpp:84:1: warning: control reaches end of non-void function [-Wreturn-type]
84 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
324 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
40 ms |
11692 KB |
Output is correct |
| 8 |
Correct |
50 ms |
11808 KB |
Output is correct |
| 9 |
Correct |
41 ms |
11720 KB |
Output is correct |
| 10 |
Correct |
47 ms |
11724 KB |
Output is correct |
| 11 |
Correct |
52 ms |
11808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
328 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
328 KB |
Output is correct |
| 10 |
Correct |
58 ms |
11732 KB |
Output is correct |
| 11 |
Correct |
60 ms |
11724 KB |
Output is correct |
| 12 |
Correct |
60 ms |
11740 KB |
Output is correct |
| 13 |
Correct |
61 ms |
11748 KB |
Output is correct |
| 14 |
Correct |
57 ms |
11744 KB |
Output is correct |
| 15 |
Correct |
74 ms |
11740 KB |
Output is correct |
| 16 |
Correct |
54 ms |
11692 KB |
Output is correct |
| 17 |
Correct |
54 ms |
10668 KB |
Output is correct |
| 18 |
Correct |
48 ms |
10324 KB |
Output is correct |
| 19 |
Correct |
52 ms |
9420 KB |
Output is correct |
| 20 |
Correct |
49 ms |
10060 KB |
Output is correct |
| 21 |
Correct |
66 ms |
11612 KB |
Output is correct |
| 22 |
Correct |
56 ms |
11576 KB |
Output is correct |
| 23 |
Correct |
69 ms |
11576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
328 KB |
Output is correct |
| 9 |
Correct |
1 ms |
320 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
328 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
324 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
324 KB |
Output is correct |
| 19 |
Correct |
1 ms |
328 KB |
Output is correct |
| 20 |
Correct |
1 ms |
324 KB |
Output is correct |
| 21 |
Correct |
1 ms |
324 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
1 ms |
340 KB |
Output is correct |
| 26 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
468 KB |
Output is correct |
| 2 |
Runtime error |
6 ms |
980 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
468 KB |
Output is correct |
| 2 |
Correct |
4 ms |
468 KB |
Output is correct |
| 3 |
Runtime error |
5 ms |
980 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
