Codeforces #816 : Div2 F. Crop Squares

Div2回ボス問がinteractiveになると、割と厄介な印象。
https://codeforces.com/contest/1715/problem/F

問題

2次元座標上で(0,0)-(n,m)の矩形領域内に、軸に平行な辺を持つ１辺1の正方形がある。
この正方形の頂点の座標は、整数とは限らない。

以下のクエリを5回まで実行し、正方形の位置を特定せよ。

• 自己交差のない1000点以下の多角形を指定し、正方形との共通部分の面積を求める。

解法

２手で解ける。
(x,y)-(x,0)-(x+1,y)-(x+1,0)-(x+2,y)....のような三角形が連なったくし形の多角形を指定するとY座標を特定できる。
Y座標が小さいほど共通部分の面積が減る。
くし形を90度回転させれば同様にX座標を特定できる。

int N,M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	double X,Y;
	
	cin>>N>>M;
	
	cout<<"? 202"<<endl;
	FOR(i,100) {
		cout<<i<<" "<<0<<endl;
		cout<<i+1<<" "<<100<<endl;
	}
	cout<<"100 101"<<endl;
	cout<<"0 101"<<endl;
	cin>>Y;
	
	cout<<"? 202"<<endl;
	FOR(i,100) {
		cout<<0<<" "<<i<<endl;
		cout<<100<<" "<<(i+1)<<endl;
	}
	cout<<"101 100"<<endl;
	cout<<"101 0"<<endl;
	cin>>X;
	
	X*=100;
	Y*=100;
	X-=0.5;
	Y-=0.5;
	cout<<"! "<<setprecision(10)<<X<<" "<<Y<<endl;
	
}

まとめ

これは賢いな…。