yukicoder : No.2831 Cos Bomb Crasher

一見ややこしいけど、理解すると簡単。
https://yukicoder.me/problems/no/2831

問題

2次元座標(-N,-N)-(N,N)の範囲に、原点O以外に2点A,Bが取られている。
ここで角AOBは直角である。

A,O,Bを囲う最小の円の半径とその中心座標を求めるインタラクティブ問題である。
クエリでは、1点Xの座標を指定すると、cos AXBの符号とcos^2 AXBの値が与えられる。
このクエリを300まで用いることができる。

解法

AOBは直角三角形であり、その外接円を求める問題である。
cos AXBの符号は、結局Xがその外接円の内外のどちらかを返してくれる。
これを使い、外接円と、X軸・Y軸の交点のうち原点以外のものを求めよう。
まず、X=(0,5.0)と(-0.5,0)のクエリを投げることで、外接円の中心のX座標の正負・0かがわかる。

仮にX座標が正だとすると、X座標を二分探索すれば外接円の交点がわかる。Y座標も以下同様。

int N;
int ask(double x,double y) {
	string s;
	cout<< std::fixed << std::setprecision(6)<<1<<" "<<x<<" "<<y<<endl;
	cin>>s>>x>>y;
	if(s=="0"||s=="?") return 0;
	if(s=="-") return -1;
	return 1;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	double X=0,Y=0;
	
	cin>>N;
	i=ask(0.5,0);
	j=ask(-0.5,0);
	if(i<0) {
		for(i=28;i>=0;i--) {
			j=ask(X+(1<<i),0);
			if(j<=0) X+=(1<<i);
		}
	}
	else if(j<0) {
		for(i=28;i>=0;i--) {
			j=ask(X-(1<<i),0);
			if(j<=0) X-=(1<<i);
		}
	}
	X/=2;
	
	i=ask(0,0.5);
	j=ask(0,-0.5);
	if(i<0) {
		for(i=28;i>=0;i--) {
			j=ask(0,Y+(1<<i));
			if(j<=0) Y+=(1<<i);
		}
	}
	else if(j<0) {
		for(i=28;i>=0;i--) {
			j=ask(0,Y-(1<<i));
			if(j<=0) Y-=(1<<i);
		}
	}
	Y/=2;
	
	cout<< std::fixed << std::setprecision(6)<<2<<" "<<X<<" "<<Y<<" "<<X*X+Y*Y<<endl;
}

まとめ

外接円が原点以外にX軸・Y軸と1点ずつ交点を持つところに気付けるかが鍵。