kmjp's blog

競技プログラミング参加記です

TopCoder SRM 668 Div2 Medium IsItASquare

なぜ600pt?
http://community.topcoder.com/stat?c=problem_statement&pm=14004

問題

2次元座標上で4つの異なる格子点が与えられる。
これらが正方形を成すか判定せよ。

解法

4つ中適当に2点A,Bを定める。ベクトル \vec{AB}を90度回転させたものをA,Bの座標に加え、それぞれの点に残り2点が対応するなら正方形。
以下はA=(x[0],y[0])固定で、Bを残り3点総当たりしている。

class IsItASquare {
	public:
	string isSquare(vector <int> x, vector <int> y) {
		int i;
		set<pair<int,int> > S;
		FOR(i,4) S.insert({x[i],y[i]});
		
		for(i=1;i<=3;i++) {
			int dx=x[i]-x[0],dy=y[i]-y[0];
			if(S.count({x[0]-dy,y[0]+dx})==0) continue;
			if(S.count({x[i]-dy,y[i]+dx})==0) continue;
			return "It's a square";
		}
		return "Not a square";
	}
}

まとめ

Div2 Mediumにしても500pt以下だと思うんだけどな。