Codeforces #445 Div1 D. Symmetric Projections

これは最初の１手が思いつかないと無理だな…。
http://codeforces.com/contest/889/problem/D

問題

２次元座標上に異なるN個の格子点の座標が与えられる。
原点を通る任意の直線に対し、N個の点を射影した点を考える。
これらの点がどこかの点に対し対象であるような元の直線の傾きは何通りあるか。

解法

選ぶ直線を平行移動すると、射影後の点も同様に平行移動する。
よって元の点を重心が原点に来るように平行移動してしまおう。
この場合、射影した後の重心も原点となるため、対象となる点の中心座標は必ず原点となるため考えやすくなる。

以後、これらの点が対称となるような射影を考えるわけだが、元もと原点を挟んで対称な位置にあるような点同士は、どんな傾きの直線を選んでも対称な位置にくるので先に取り除いてしまおう。
結果全頂点が取り除けてしまった場合、元の点が原点に対象なわけなのでどんな傾きの直線をとっても対象になる。

以下残りのケースを考える。
全頂点対について、それらが射影後原点を挟んで対称位置に来るような直線の傾きを考えよう。
これは簡単で、原点から２頂点の中点へのベクトルを考えれば、それと直角な直線が条件を満たす。
こうしてO(N^2)通りの直線を考える。

さて、題意を満たす直線は、全頂点に対し射影後対称となる点がなければならないので、O(N^2)通りの直線を考えるとN回以上登場するはずである。
そのような直線は高々N本しかないので、改めてそのような直線に実際に射影したとき点対象となるか判定すればよい。
事前に頂点座標を整数倍するなど、うまく気を付けて計算すれば、すべてlong longの範囲で計算でき小数は不要である。

int N;
ll X[2020],Y[2020];
int avail[2020];

int check(ll sx,ll sy) {
	vector<pair<ll,ll>> V;
	int i;
	FOR(i,N) {
		ll x=(sy==0)?0:(X[i]*sy-sx*Y[i]);
		ll y=(sx==0)?0:(sx*Y[i]-X[i]*sy);
		V.push_back({x,y});
	}
	sort(ALL(V));
	int L=0,R=V.size()-1;
	while(L<=R) {
		if(V[L].first!=-V[R].first || V[L].second!=-V[R].second) return 0;
		L++;
		R--;
	}
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll SX=0,SY=0;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		X[i]*=2*N;
		Y[i]*=2*N;
		SX+=X[i];
		SY+=Y[i];
	}
	SX/=N;
	SY/=N;
	FOR(i,N) X[i]-=SX,Y[i]-=SY,avail[i]=1;
	FOR(x,N) if(avail[x]) {
		FOR(y,N) if(avail[y]) {
			if(X[x]+X[y]==0 && Y[x]+Y[y]==0) {
				avail[x]=avail[y]=0;
				break;
			}
		}
	}
	vector<pair<ll,ll>> V;
	FOR(i,N) if(avail[i]) V.push_back({X[i],Y[i]});
	FOR(i,V.size()) X[i]=V[i].first,Y[i]=V[i].second;
	N=V.size();
	
	if(N==0) return _P("-1\n");
	
	vector<pair<ll,ll>> cand;
	FOR(y,N) FOR(x,N) {
		ll sx=(X[x]+X[y])/2;
		ll sy=(Y[x]+Y[y])/2;
		ll g=__gcd(abs(sx),abs(sy));
		sx/=g;
		sy/=g;
		if(sx<0) sx=-sx, sy=-sy;
		if(sx==0 && sy<0) sy=-sy;
		cand.push_back({sx,sy});
	}
	
	int ret=0;
	sort(ALL(cand));
	pair<ll,ll> pre={0,0};
	int cnt=0;
	FORR(r,cand) {
		if(pre!=r) pre=r, cnt=0;
		cnt++;
		if(cnt==N) ret+=check(r.first,r.second);
	}
	
	cout<<ret<<endl;
}

まとめ

最初の平行移動さえ思いつけば行けたかもな。