题目传送门:http://codeforces.com/contest/714/problem/D
CF上做的第一道交互题!
然而考场上并没能A掉QAQ
就是二分出几个关键点,然后暴力问一问
#include<bits/stdc++.h> #define LL long long using namespace std; int n,x[5],y[5],vout[10]; inline int read(){ 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); return read(); } 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(){ n = read(); 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; }