CSAcademy Round #38 : G. Parallel Lines

何気に定数倍が厳しい。
https://csacademy.com/contest/round-38/task/parallel-lines/

問題

２次元座標上でN個の格子点の座標が与えられる。
これらの点を、何本かの平行な直線で覆うには、最小何本必要か。
なお、解をKとするとKは400以下である。

解法

まずY軸に平行なケースは全頂点のユニークなX座標の数を数えるだけなので容易に計算できる。
あとはY軸に平行でないケースを考えよう。
この場合、傾きを決めれば各頂点を通るY切片の数がそのまま直線の数になる。

２頂点を結ぶ頂点から傾きの候補を決め、対応して各頂点を通るY切片の数を逐次決めていってもよいが、愚直にやるとO(N^3)でTLEする。
そこでKの条件を用いて高速化しよう。

• Nが2K以下の場合
  • 愚直解をちょっと高速化する。頂点U-Vを結ぶ直線の傾きを解の候補とする。この時、VのX座標の方が大きいならば、傾きと対応してVを新たなY切片を生成しない頂点として覚えておこう。
  • 仮にA-B-C-D-Eと一直線に並ぶ場合、同様の処理を各頂点対に行えば、B,C,D,Eは新たなY切片を生成しないので、結果AだけがY切片を増やし、直線は1本だけ追加となる。
  • このためには傾きをキーとし、Y切片を生成しない頂点群の集合を値とする連想配列を使って管理すればよい。Y切片を生成しない頂点数が最多の傾きが解の直線となる。
• Nが2Kを超える場合
  • まず先頭2K頂点に対し、上記同様にY切片の数をカウントしよう。
  • 解がK以下なので、この時点でY切片の数がK以下のものだけ残し、以後N頂点に対しY切片の数を数えていく。

全体的にmapやunordered_mapを使うとTLEが厳しいので、vectorをsortするなどして高速化しよう。

int T,N;
pair<int,int> P[30303];
ll tmp[303030];

ll myhash(int a,int b) {
	return ((ll)a<<32)+b;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		set<int> xs;
		FOR(i,N) cin>>P[i].first>>P[i].second, xs.insert(P[i].first);
		int ret=xs.size();
		sort(P,P+N);
		
		if(N<=810) {
			unordered_map<ll,vector<int>> did;
			FOR(y,N) FOR(x,y) {
				if(P[x].first==P[y].first) continue;
				int a=P[y].second-P[x].second;
				int b=P[y].first-P[x].first;
				
				int g=__gcd(a,b);
				did[myhash(a/g,b/g)].push_back(y);
			}
			
			FORR(r,did) {
				sort(ALL(r.second));
				r.second.erase(unique(ALL(r.second)),r.second.end());
				ret=min(ret,N-(int)r.second.size());
			}
			
		}
		else {
			vector<pair<int,int>> cand;
			FOR(y,800) FOR(x,y) {
				int a=P[x].second-P[y].second;
				int b=P[x].first-P[y].first;
				if(b==0) continue;
				int g=__gcd(a,b);
				cand.push_back({a/g,b/g});
			}
			sort(ALL(cand));
			cand.push_back({0,0});
			
			int prev=-1;
			for(i=1;i<cand.size();i++) if(cand[i]!=cand[i-1]) {
				int num=(i-1)-prev;
				if(num>=400) {
					ll a=cand[i-1].first, b=cand[i-1].second;
					FOR(j,N) tmp[j]=P[j].second*b-a*P[j].first;
					sort(tmp,tmp+N);
					x=unique(tmp,tmp+N)-tmp;
					ret=min(ret,x);
				}
				prev=i-1;
			}
		}
		cout<<ret<<endl;
		
		
		
	}
}

まとめ

細かい高速化があまり問題の本題ではないので、Kが100～200位でもよかった気はするな。