【Codeforces 713B】Searching Rectangles

题目传送门: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;
}