发现没有 sol，所以来复读一下官方题解。

考虑直线上方和下方点集构成的凸包，我们声称：

定理 1：令 $\epsilon \approx \dfrac{1}{2V}$，那么答案一定可以被表示成直线上方凸包的一条边向下平移 $\epsilon$ 或直线下方凸包的一条边向上平移 $\epsilon$。

证明是初中几何，这里就不再重复了。

接下来考虑两侧凸包的性质，只讨论下方的凸包，因为上方的凸包是同理的。

定理 2：凸包的点数不超过 $2\log_2 V$。

我们分 $2$ 步证明。在特殊性质 A 中，如果凸包包含 $(x,y)$，那么它一定包含 $(2x,2y)$，故除 $(0,0)$ 外左侧第一个点的横坐标一定大于 $\dfrac{V}{2}$，把 $(x_1,y_1)$ 平移到 $(0,0)$ 删去，凸包仍要满足上述性质，凸包点数为 $\log_2 V$。接下来，直接取平面中最接近直线的整点为原点，就可以得到 $2$ 个具有特殊性质 A 的平面，故凸包总点数不超过 $2\log_2 V$。

根据以上定理，我们只需要求出一些点使得它们能还原出原凸包即可求解。

首先，我们用 $2\log_2 V$ 次询问得到 $L(0)$ 和 $L(V)$。于是，问题变成了给你一个 $n\times (m+1)$ 大小的二维平面，保证直线和 $(0,0),(0,1)$ 这条线段有交，和 $(n,m),(n,m+1)$ 这条线段有交。

显然，如果有 $m\ge n$，有简单坐标变换：$(x,y)\to (x,y-\lfloor\dfrac{n}{m}\rfloor x)$，容易证明得到的结果是不变的（相当于凸包加直线）。

否则，可以通过 $2\log_2 \dfrac{n}{m}$ 次询问得到第一个 $L(x)\ge 1$ 和第一个 $L(x)\ge m$，然后交换坐标轴做子问题。大概形如下图：

证明一下询问次数：$T(n,m)=T(m-1,(n-k)\bmod ({m-1}))+2\log_2\dfrac{n}{m}$，其中 $k\le 2\dfrac{n}{m}$, 显然是 $O(\log V)$ 的，因为 $n>m>0$，所以一定有 $n-k\ge m-1$，故每次 $n$ 至少减半。可以分析出查询次数 $\le 4\log V$。

关于时间复杂度：如果你用几个变量维护坐标变换，再 $O(\log)$ 凸包上查询是否存在点在直线下的话，可以做到 $O(\log V\log\log V)$，当然，$O(\log^2 V)$ 也是可以过的。

```cpp
#include "plain.h"
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
map<pair<int,int>,int>Q;
inline int qry(int x,int y){
	return Q.count({x,y})?Q[{x,y}]:Q[{x,y}]=query(x,y);
}
template<class T>inline pair<T,T>operator-(const pair<T,T>&x,const pair<T,T>&y){
	return make_pair(x.first-y.first,x.second-y.second);
}
inline LL cross(const pair<int,int>&x,const pair<int,int>&y){
	return 1ll*x.first*y.second-1ll*x.second*y.first;
}
pair<vector<pair<int,int>>,vector<pair<int,int>>>
	solve(int n,int m,function<int(int,int)>X,function<int(int,int)>Y,bool flg){
	if(!m){
		vector<pair<int,int>>L,R;
		L.emplace_back(X(0,0),Y(0,0));
		L.emplace_back(X(n,0),Y(n,0));
		R.emplace_back(X(0,1),Y(0,1));
		R.emplace_back(X(n,1),Y(n,1));
		return make_pair(L,R);
	}
	if(m/n){
		function<int(int,int)>nX=[&](int x,int y){return X(x,y+m/n*x);};
		function<int(int,int)>nY=[&](int x,int y){return Y(x,y+m/n*x);};
		return solve(n,m%n,nX,nY,flg);
	}
	vector<pair<int,int>>L,R;
	int px=0,py=1;
	for(int l=1,r=(n-1)/m;l<=r;){
		const int mid=(l+r)>>1;
		if(!(qry(X(mid,py),Y(mid,py))^flg))px=mid,l=mid+1;
		else r=mid-1;
	}
	int qx=(m-1ll)*n/m,qy=m;
	for(int l=(m-1ll)*n/m+1,r=n-1;l<=r;){
		const int mid=(l+r)>>1;
		if(!(qry(X(mid,qy),Y(mid,qy))^flg))qx=mid,l=mid+1;
		else r=mid-1;
	}
	function<int(int,int)>nX=[&](int x,int y){return X(y+px,x+py);};
	function<int(int,int)>nY=[&](int x,int y){return Y(y+px,x+py);};
	tie(R,L)=solve(qy-py,qx-px,nX,nY,!flg);
	L.emplace_back(X(0,0),Y(0,0));
	L.emplace_back(X(n,m),Y(n,m));
	R.emplace_back(X(0,1),Y(0,1));
	R.emplace_back(X(n,m+1),Y(n,m+1));
	return make_pair(L,R);
}
inline vector<pair<int,int>>convex(vector<pair<int,int>>A,bool op){
	sort(A.begin(),A.end());
	if(op)reverse(A.begin(),A.end());
	A.erase(unique(A.begin(),A.end()),A.end());
	vector<pair<int,int>>B;
	for(auto p:A){
		while(B.size()>1&&cross(B.back()-B.end()[-2],p-B.end()[-2])<=0)B.pop_back();
		B.emplace_back(p);
	}
	if(op)reverse(B.begin(),B.end());
	return B;
}
tuple<LL,int,LL,int>Find(int,int n,int){
	Q.clear();
	int y0=0;
	for(int l=1,r=n-1;l<=r;){
		const int mid=(l+r)>>1;
		if(qry(0,mid))y0=mid,l=mid+1;
		else r=mid-1;
	}
	int yn=0;
	for(int l=1,r=n-1;l<=r;){
		const int mid=(l+r)>>1;
		if(qry(n,mid))yn=mid,l=mid+1;
		else r=mid-1;
	}
	vector<pair<int,int>>L,R;
	if(y0<=yn){
		function<int(int,int)>X=[&](int x,int y){return x;};
		function<int(int,int)>Y=[&](int x,int y){return y+y0;};
		tie(L,R)=solve(n,yn-y0,X,Y,0);
	}
	else{
		function<int(int,int)>X=[&](int x,int y){return n-x;};
		function<int(int,int)>Y=[&](int x,int y){return y+yn;};
		tie(L,R)=solve(n,y0-yn,X,Y,0);
	}
	L=convex(L,1),R=convex(R,0);
	const auto Line=[&](pair<int,int>a,pair<int,int>b){
		LL ks=a.second-b.second;
		int kt=a.first-b.first;
		if(kt<0)ks*=-1,kt*=-1;
		LL bs=1ll*a.second*kt-1ll*a.first*ks;
		int bt=kt;
		return make_tuple(ks,kt,bs,bt);
	};
	const auto check=[&](tuple<LL,int,LL,int> line){
		auto&[ks,kt,bs,bt]=line;
		for(auto [x,y]:L)if((LLL)ks*x*bt+(LLL)bs*kt<=(LLL)y*kt*bt)return 0;
		for(auto [x,y]:R)if((LLL)ks*x*bt+(LLL)bs*kt>=(LLL)y*kt*bt)return 0;
		return 1;
	};
	for(int i=0;i+1<L.size();++i){
		auto line=Line(L[i],L[i+1]);
		int r=(n+n)/get<3>(line);
		get<2>(line)*=r,get<3>(line)*=r,++get<2>(line);
		if(check(line))return line;
	}
	for(int i=0;i+1<R.size();++i){
		auto line=Line(R[i],R[i+1]);
		int r=(n+n)/get<3>(line);
		get<2>(line)*=r,get<3>(line)*=r,--get<2>(line);
		if(check(line))return line;
	}
	return make_tuple(-1,-1,-1,-1);
}
/*
*/