Codeforces #870 : Div2 F. Fading into Fog

また変な制限。
https://codeforces.com/contest/1826/problem/F

問題

2次元上のN個の点の位置を答えるインタラクティブ問題である。
直線を1つ指定すると、各点をその直線に射影した座標を、ランダムな順で返す。
ただし最大0.0001ほど誤差がある。

このクエリを最小回数使い、すべての点の座標を求めよ。

解法

まず直線でX軸とY軸を指定すると、X座標とY座標のsetがそれぞれ求められる。
次に、原点を通る適当な角度の直線を指定することを考える。
N個のX座標とN個のY座標からなるN^2個の点が、0.0001以上の距離に分布するような角度を乱択で求め、それを使おう。

int T,N;
double X[202],Y[202];
double RX[202],RY[202];
mt19937 engine(0);



void solve() {
	int i,j,k,l,r,x,y; string s;
	double PI=atan(1)*4;
	uniform_real_distribution<double> UD(0,PI);
	
	cin>>T;
	while(T--) {
		cin>>N;
		cout<<"? 1 0 0"<<endl;
		FOR(i,N) cin>>Y[200]>>Y[i];
		cout<<"? 0 1 0"<<endl;
		FOR(i,N) cin>>X[i]>>X[200];
		double deg;
		vector<pair<double,double>> P;
		while(1) {
			deg=UD(engine);
			P.clear();
			double a=cos(deg),b=sin(deg);
			FOR(y,N) FOR(x,N) {
				double dot=X[x]*a+Y[y]*b;
				P.push_back({dot*a,dot*b});
			}
			int ok=1;
			FOR(x,P.size()) FOR(y,x) {
				if(abs(P[x].first-P[y].first)<0.001&&abs(P[x].second-P[y].second)<0.001) ok=0;
			}
			if(ok==1) break;
		}
		cout<<std::setprecision(12)<<"? "<<-sin(deg)<<" "<<cos(deg)<<" 0"<<endl;
		vector<pair<double,double>> ret;
		FOR(i,N) {
			double rx,ry;
			cin>>rx>>ry;
			FOR(y,N) FOR(x,N) {
				if(abs(rx-P[y*N+x].first)<0.0004&&abs(ry-P[y*N+x].second)<0.0004) ret.push_back({X[x],Y[y]});
			}
		}
		assert(ret.size()==N);
		
		cout<<"!";
		FOR(i,N) cout<<std::setprecision(12)<<" "<<ret[i].first<<" "<<ret[i].second;
		cout<<endl;
	}
}

まとめ

わかってしまえばシンプルな問題。