题解
人生第一道交互题，感觉很神奇（还好并不难）
考虑以下情况：
- 如果我们没有框中头尾，势必有一条“进入”矩形的边，就有一条“出去”的边。
- 如果我们只框中头或尾，肯定少一条“进入”或“出去”的边。
- 如果我们同时框中了头尾，肯定少两条“进入”或“出去”的边。
综上，当ask的答案为奇数时，我们框中了头或尾，为偶数时可能同时框中，可能同时没框中。
可以先确定头尾是否在同一列
- 不在同一列，分别对它们所在列二分，找到对应的点。
- 在同一列，再二分行数，找到对应的点。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include<bits/stdc++.h> using namespace std; int n,x; int x_1,y_1,x_2,y_2;int i,j; int ask(int x,int y,int z,int k){ printf("? %d %d %d %d\n",x,y,z,k); fflush(stdout); int ans; cin>>ans; return ans; } int main(){ cin>>n; for(i=1;i<n;i++)if(ask(1,1,n,i)&1)break; if(i!=n){ for(j=n;j>1;j--)if(ask(1,j,n,n)&1)break; int l=1,r=n; while(l<r){ int mid=(l+r+1)>>1; if(ask(mid,i,n,i)&1)l=mid; else r=mid-1; } x_1=l;y_1=i; l=1,r=n; while(l<r){ int mid=(l+r+1)>>1; if(ask(mid,j,n,j)&1)l=mid; else r=mid-1; } x_2=l,y_2=j; } else { for(i=1;i<n;i++)if(ask(1,1,i,n)&1)break; for(j=n;j>1;j--)if(ask(j,1,n,n)&1)break; int l=1,r=n; while(l<r){ int mid=(l+r+1)>>1; if(ask(i,mid,i,n)&1)l=mid; else r=mid-1; } x_1=i;y_1=l; l=1,r=n; while(l<r){ int mid=(l+r+1)>>1; if(ask(j,mid,j,n)&1)l=mid; else r=mid-1; } x_2=j,y_2=l; } printf("! %d %d %d %d\n",x_1,y_1,x_2,y_2); return 0; } |