第3回 ドワンゴからの挑戦状 本選 : C - ドワンGo

これは方針思いつくかどうかだな…。
http://dwacon2017-honsen.contest.atcoder.jp/tasks/dwango2017final_c

問題

2次元座標上、(0,0)-(10^6,10^6)の矩形範囲のいずれかの格子点を中心とする半径10^5の円がある。
座標を指定すると、その点が円の内部にあるかどうかがわかるクエリがある。
このクエリを最大200回用いて、中心点を求めよ。

解法

まずはおおよその円の位置を求めよう。
1.25*10^5毎に座標をずらしながらクエリを投げれば、64回以内に1回は必ず円の内部にあたる。
円の内部を求めたら、左右方向それぞれに二分探索し、そのY座標に対応するX座標の最大値最小値を求めよう。
こうすると円周上の点が2つ求められるので、あとは垂直二等分線上に中心点の候補が2つ現れるのでそれを両方試せばよい。

ll L=1000000,R=100000;

int ask(double x,double y,bool round=false) {
	char result[10];
	if(round) {
		printf("%lld %lld\n", (ll)(0.1+x), (ll)(0.1+y));
	}
	else {
		printf("%.9f %.9f\n", x, y);
	}
	fflush(stdout);
	scanf("%s", result);
	
	if(strcmp(result,"found")==0) exit(0);
	return strcmp(result,"close")==0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	ll S=R*5/4, D=S/2;
	
	ll X,Y;
	for(X=D;X<L;X+=S) for(Y=D;Y<L;Y+=S) if(ask(X,Y,true)) goto out;
	assert(0);
	out:
	double XL=X,XR=X;
	double d=1e6;
	FOR(i,60) {
		if(ask(XR+d,Y)) XR+=d;
		if(ask(XL-d,Y)) XL-=d;
		d/=2;
	}
	double XC=(XL+XR)/2;
	double DY=sqrt(R*R-(XC-XL)*(XC-XL));
	ask(XC,Y-DY,true);
	ask(XC,Y+DY,true);
	
}

まとめ

これ本番出てたら自分で思いつけてたかな…どうかな。