UTPC 2014 : H - 回すだけ

これ、本番中は手を出さなかったけど愚直にやれば自力で解けた…。
http://utpc2014.contest.atcoder.jp/tasks/utpc2014_h

問題

2次元座標上に凸多角形がある。
この凸多角形は以下の条件を満たす。

• 各頂点は格子点にあり、頂点の1つは原点にある。その他の頂点はY座標が負である。
• 各角の角度は170度以下である。
• 頂点数は10以下である。
• 各頂点の座標の絶対値は1000以下である。

この多角形に対し、回転角度を指定して問い合わせを行うと、多角形をその分反時計回りに回転して得られる多角形のうち、Y座標の最大値が得られる。
問い合わせ回数1000回以内でこの図形の頂点を確定せよ。

解法

図形を少しずつ左回転させていき、1個ずつ頂点を確定させていく。
初期は原点しか頂点がわからないが、徐々に図形を回転させるとそのうち返ってくるY座標が正になりだす。
これは未知の頂点が最もY座標が上に来たことを示す。
もう少し回してもう少しY座標が上になるようにすると、2回の回転角とY座標から、回転前の位置を特定できる。

その後、また徐々に回転させて既知の頂点から算出できないY座標が登場したら、新規頂点として開店前の位置を求める…というのを繰り返せばよい。

double ask(double ang) {
	double ymax;
	printf("? %.12lf\n", ang);
	fflush(stdout);
	scanf("%lf", &ymax);
	return ymax;
}

void solve() {
	int i,j,k,l,r; string s;
	double deg[2000];
	
	double pi=acos(-1);
	vector<pair<int,int> > V;
	V.emplace_back(0,0);
	
	for(i=0;i<=720;i++) {
		deg[i] = ask(i*0.5);
		if(i<2) continue;
		int cy=V.back().second, cx=V.back().first;
		double dc =i*0.5*pi/180, dp=(i-1)*0.5*pi/180;
		double c1=cos(dc),s1=sin(dc);
		double c2=cos(dp),s2=sin(dp);
		
		double y1=deg[i], y2=deg[i-1];
		if(y1 < cy*c1+cx*s1+0.00001 || y2 < cy*c2+cx*s2+0.00001) continue;
		
		double x,y;
		y=(y1*s2-y2*s1)/(c1*s2-c2*s1);
		x=(y1*c2-y2*c1)/(c2*s1-c1*s2);
		V.emplace_back(floor(x+0.5),floor(y+0.5));
	}
	
	_P("! %d\n",V.size()-1);
	FOR(i,V.size()-1) _P("! %d %d\n",V[V.size()-1-i].first,V[V.size()-1-i].second);
}

まとめ

結果的に自力で解けたんだし、本番解けばよかったな。