CODE FESTIVAL 2014 上海 : C - Regular Polygon

同じような問題は考えたことがあったのでこれは楽だった。
http://code-festival-2014-china-open.contest.atcoder.jp/tasks/code_festival_china_c

問題

２次元座標上でN個の異なる位置の格子点の座標が与えられる。
これらのうち幾つかを線分でつなげて正多角形を作りたい。

作成可能な正多角形のうち、頂点数が最大のものを答えよ。

解法

実はこれ、正方形しか条件に合わない。
正三角形や正八角形あたりを作ろうとするとどうしてもどこかの座標に平方根が登場してしまう。

後は正方形を探すだけである。
２点を総当たりすると、残り２点の座標が確定するので、その残り２点の座標に頂点が存在するかsetで調べればよい。

以下のコードでは、２点を定めて残り２点を時計回り順に計算しているが、対角線を成す２点を総当たりしても良い。

map<pair<ll,ll>,int > M;
int N;
ll X[1010],Y[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		M[make_pair(X[i],Y[i])]=i;
	}
	
	FOR(x,N) FOR(y,N) if(x!=y) {
		ll x2,y2,x3,y3;
		x2=X[y]+(Y[y]-Y[x]);
		y2=Y[y]-(X[y]-X[x]);
		x3=X[x]+(Y[y]-Y[x]);
		y3=Y[x]-(X[y]-X[x]);
		if(M.count(make_pair(x2,y2)) && M.count(make_pair(x3,y3))) {
			vector<int> V;
			V.push_back(x+1);
			V.push_back(y+1);
			V.push_back(M[make_pair(x2,y2)]+1);
			V.push_back(M[make_pair(x3,y3)]+1);
			sort(ALL(V));
			_P("4\n");
			FOR(i,4) _P("%d\n",V[i]);
			return;
		}
	}
	_P("0\n");
	
}

まとめ

O(N^2*logN)の正方形探索とO(N^3*logN)の長方形探索は考えたことあったけど、今回で前者は使われてしまったので今後出せないな…。