TopCoder SRM 674 Div2 Medium PlaneGame

EasyもMediumも1発正答だったけど、Easyに時間かかりすぎたので結果的に出なくて正解か。
https://community.topcoder.com/stat?c=problem_statement&pm=14007

問題

2次元座標上でN個の異なる点が与えられる。
これらの点を、以下の通りに移動可能とする。

• 全点を同じ向き・距離に平行移動できる
• 全点を同じ原点と中心とし、同じ角度だけ回転できる。

そののち、X軸上またはY軸上にある点に対して攻撃を仕掛けられる。
適切に点を移動した場合、最大で同時に何個の点に攻撃できるか。

解法

点が動くと考えるとややこしいので、任意の1本の直線とそこに垂直なもう1本の直線上の点に攻撃可能と考える。
N<=2の時は2点を1本の直線上に乗せられるので、2点に攻撃可能なのは明らか。
よって以下N＞2のケースを考えよう。

まず確実に撃ちぬく2つの点x,yを総当たりしながら、攻撃可能な最大点数を求めよう。
2点が決まった時点で、2本の直線のうち1本は確定するので、まずこの直線状の点は確実に攻撃できる。
あとは、直線xyを90度回転させたものを考える。
残された各頂点について、そこを通るようこの90度回転させた直線を攻撃対象とすると、後何頂点そこに乗るかを求め、その最大値を求めればよい。

class PlaneGame {
	public:
	
	int how(vector<int> x,vector<int> y,ll dx,ll dy) {
		int ma=0,a,b;
		FOR(a,x.size()) {
			int cnt=0;
			FOR(b,x.size()) {
				if((x[b]-x[a])*dy-(y[b]-y[a])*dx==0) cnt++;
			}
			ma=max(ma,cnt);
		}
		return ma;
	}
	
	int bestShot(vector <int> x, vector <int> y) {
		int N=x.size();
		int a,b,c;
		
		if(N<=2) return N;
		
		int ma=2;
		FOR(b,N) FOR(a,b) {
			vector<int> x2,y2;
			FOR(c,N) {
				ll cr = 1LL*(x[c]-x[a])*(y[b]-y[a])-1LL*(y[c]-y[a])*(x[b]-x[a]);
				if(cr) x2.push_back(x[c]), y2.push_back(y[c]);
			}
			ma=max(ma,(N-(int)x2.size()) + how(x2,y2,-(y[b]-y[a]),(x[b]-x[a])));
		}
		
		return ma;
	}
}

まとめ

意外と正答率低い問題だったね。