我永远喜欢39号同学2018。

· · 题解

先发一篇通过 7 次询问获得答案的方法。感觉还能优化。以后想到了新算法再更新。

基础:平面直角坐标系(否则题目都看不懂)，有基本的几何知识(本题需要用到等腰直角三角形和矩形(长方形)的性质)。学完了整数(int)的定义和输入(cin/scanf)输出(cout/printf)。

为方便题解叙述，有些地方将会用到函数。

题目大意

有一个矩形，四条边都平行于坐标轴。其中任意一点的范围都在开区间 (1,10^9) 范围内。且顶点为整点。

每次询问可以选择一个矩形外的整点并得知与矩形的最近曼哈顿距离(即只走平行于坐标轴的路线到达矩形)。

最多用 40 次询问猜出矩形。选择的点的 x,y 值应均在闭区间 [1,10^9] 内。

12 次询问

先假设边界在 [0,10^9] 。最后询问出来的结果加一即可。

(保证询问合法) 只能选取矩形外的点，而它的坐标范围又是开区间。取不到 0 和 10^9，那么选取这些地方一定不会选在矩形内。

先考虑查询出矩形底端的 y 轴。

先来看一张图,图中的下边界就是 x 轴。红色数字表示它与矩形的距离。

可以发现,距离一定是由三段斜率分别为 -1,0,1 的一次函数构成。形如下图:

证明过程不难,列式子推就可以了。

(求出底端距离) 发现下面那一段平(斜率为 0)的就是矩形底端到 x 轴的距离。现在只要找出底端线段上的一个整点就可以通过一次询问知道矩形底端到 x 轴的距离。

找单峰函数的底端需要用到三分。但是会TLE(后续还需要进行其它询问)。

(寻找函数特殊规律) 发现这个函数的第一段和第三段斜率是一样的。因此将其延长，交点的 x 坐标一定是它们终点 x 坐标的平均值。(如下图)

现在的问题就是如何找到这个平均值。

(调整到同一水平高度) 任意的两点,如果水平高度相同，那么它们 x 坐标的平均值恰好就是我们要求的平均值。可以用等腰直角三角形的一些性质来证明。

由于斜率已知,我们很容易根据 y 坐标差值算出 x 坐标差值，从而得到 x 坐标，算它们的平均数就很容易了。如下图:

如果平均值不是整数，那么它向上取整或向下取整都是可以的。

为保证每次查询的两个点一定分别在第一段和第三段，那么第一个点选为 (0,0)，第二个点选为 (0,10^{9})。

然后查询左端距 y 轴的距离，上端到边界(直线 y=10^9 )，右端到边界(直线 x=10^9)

8 次询问

其实这个比 12 次还好实现些。

(避免重复询问) 发现有(0,0),(0,10^9),(10^9,0),(10^9,10^9) 这 4 个点实际上重复询问了一次。所以可以一开始就询问这 4 个点来实现预处理。

代码:

#include<iostream>
#include<cmath>
using namespace std;
#define N 1000000000 //表示边界10^9
int Q(int x,int y){ //处理一次询问。
    int ans;
    cout<<"? "<<x<<" "<<y<<endl;
    cin>>ans;
    return ans;
}
int main(){
    int ans0,ans1,ans2,ans3,disl,disr,disd,disu;
    ans0=Q(1,N); //预处理4个角。
    ans1=Q(N,N);
    ans2=Q(1,1);
    ans3=Q(N,1);
    disd=Q((N-(ans3-ans2)+1)/2,1); //求出底端距离。
    disl=Q(1,(N-(ans0-ans2)+1)/2); //求出左端距离。
    disu=Q((N-(ans1-ans0)+1)/2,N); //求出顶端距离。
    disr=Q(N,(N-(ans1-ans3)+1)/2); //求出右端距离。
    cout<<"! "<<disl+1<<" "<<disd+1<<" "<<N-disr<<" "<<N-disu<<endl; //disl和disd要加一。因为在本篇题解中左边界和下边界是被认作是0。
    return 0;
}

7 次询问

以上算法足以通过本题。但还是可以继续优化。

由于矩形平行于坐标轴，所以如果一个点在底端一定存在一个 x 轴与它相同的点在顶端。如下图:

同理,如果一个点在左端一定存在一个 y 轴与它相同的点在右端。

因此可以将代码改为(仅展示核心代码):

    disd=Q((N-(ans3-ans2)+1)/2,1);
    disl=Q(1,(N-(ans0-ans2)+1)/2);
    disu=Q((N-(ans3-ans2)+1)/2,N);
    disr=Q(N,(N-(ans0-ans2)+1)/2);

现在不需要用到 ans1 了。所以就少了一次询问。