## 【Codeforces 713B】Searching Rectangles

CF上做的第一道交互题！

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int n,x[5],y[5],vout[10];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline int judge(int _x1,int _y1,int _x2,int _y2) {
printf("? %d %d %d %d\n",_x1,_y1,_x2,_y2);
fflush(stdout);
}

inline bool BETTER(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4){
if (!vout[1]) return true;
LL s1 = (LL)(vout[3]-vout[1] + 1)*(vout[4]-vout[2] + 1) + (LL)(vout[7]-vout[5] + 1)*(vout[8]-vout[6] + 1);
LL s2 = (LL)(x2 - x1 + 1) * (y2 - y1 + 1) + (LL)(x4 - x3 + 1) * (y4 - y3 + 1);
return s2 < s1;
}

int main(){
int l = 1, r = n, mid, ret;
while (l <= r) {
mid = l + r >> 1;
if (judge(1,1,mid,n) >= 1) ret = mid, r = mid-1;
else l = mid+1;
} x[1] = ret;
l = ret, r = n, ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (judge(1,1,mid,n) >= 2) ret = mid, r = mid-1;
else l = mid+1;
} x[3] = ret;
l = 1, r = n, ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (judge(mid,1,n,n) >= 1) ret = mid, l = mid+1;
else r = mid-1;
} x[2] = ret;
l = 1, r = x[2], ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (judge(mid,1,n,n) >= 2) ret = mid, l = mid+1;
else r = mid - 1;
} x[4] = ret;

l = 1, r = n, ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (judge(1,1,n,mid) >= 1) ret = mid, r = mid-1;
else l = mid+1;
} y[1] = ret;
l = y[1], r = n, ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (judge(1,1,n,mid) >= 2) ret = mid, r = mid-1;
else l = mid+1;
} y[3] = ret;
l = 1, r = n, ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (judge(1,mid,n,n) >= 1) ret = mid, l = mid+1;
else r = mid-1;
} y[2] = ret;
l = 1, r = y[2], ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (judge(1,mid,n,n) >= 2) ret = mid, l = mid+1;
else r = mid-1;
} y[4] = ret;

sort(x+1,x+5); sort(y+1,y+5);
for (int s=1;s<=4;s++) for (int i=s+1;i<=4;i++) for (int j=1;j<=4;j++) for (int k=j+1;k<=4;k++)
if (judge(x[s],y[j],x[i],y[k]) == 1) { int x1,x2,y1,y2;
for (int u=1;u<=4;u++) if (u != i && u != s) {x1=u; break;}
for (int u=x1+1;u<=4;u++) if (u != i && u != s) {x2=u; break;}
for (int u=1;u<=4;u++) if (u != j && u != k) {y1 = u; break;}
for (int u=y1+1;u<=4;u++) if (u != j && u != k) {y2=u;break;}
if (x[x1] > x[i] || x[x2] < x[s] || y[y1] > y[k] || y[y2] < y[j])
if (judge(x[x1],y[y1],x[x2],y[y2]) == 1 && BETTER(x[s],y[j],x[i],y[k],x[x1],y[y1],x[x2],y[y2]))
vout[1]=x[s],vout[2]=y[j],vout[3]=x[i],vout[4]=y[k],vout[5]=x[x1],vout[6]=y[y1],vout[7]=x[x2],vout[8]=y[y2];
}
putchar('!');
for (int i=1;i<=8;i++) printf(" %d",vout[i]);
return 0;
}