题目链接：洛谷
这道题是很久以前NTF跟我说的，现在想起来把它做了。。。
我们发现，如果蛇的两头都在矩形里或矩形外，则询问为偶数，否则为奇数。
所以我们询问每一行和每一列，就能知道蛇的两头的横纵坐标了。
但是有一种情况不行，那就是两头在同一行或列上（以下只考虑同一行的），但是它们一定不在同一列，所以可以找到它们所在的列，然后通过二分找出它们所在的行。
具体实现可以看代码。
1 #include<bits/stdc++.h> 2 #define Rint register int 3 using namespace std; 4 inline int read(){ 5 int ch = getchar(), res = 0; 6 while(ch < ‘0‘ || ch > ‘9‘) ch = getchar(); 7 while(ch >= ‘0‘ && ch <= ‘9‘){ 8 res = res * 10 + ch - ‘0‘; 9 ch = getchar(); 10 } 11 return res; 12 } 13 int n, cnt; 14 pair<int, int> res[4]; 15 inline int query(int a1, int b1, int a2, int b2){ 16 printf("? %d %d %d %d\n", a1, b1, a2, b2); 17 fflush(stdout); 18 return read() & 1; 19 } 20 inline int solve1(int x){ 21 int l = 1, r = n, mid; 22 while(l < r){ 23 mid = l + r >> 1; 24 if(query(x, l, x, mid)) r = mid; 25 else l = mid + 1; 26 } 27 return l; 28 } 29 inline int solve2(int x){ 30 int l = 1, r = n, mid; 31 while(l < r){ 32 mid = l + r >> 1; 33 if(query(l, x, mid, x)) r = mid; 34 else l = mid + 1; 35 } 36 return l; 37 } 38 int main(){ 39 n = read(); 40 for(Rint i = 1;i <= n;i ++) 41 if(query(i, 1, i, n)) res[cnt ++] = make_pair(i, solve1(i)); 42 if(!cnt){ 43 for(Rint i = 1;i <= n;i ++) 44 if(query(1, i, n, i)){ 45 if(!cnt) res[cnt ++] = make_pair(solve2(i), i); 46 else res[cnt ++] = make_pair(res[0].first, i); 47 } 48 } 49 printf("! %d %d %d %d\n", res[0].first, res[0].second, res[1].first, res[1].second); 50 fflush(stdout); 51 }
原文：https://www.cnblogs.com/AThousandMoons/p/11107941.html
