kmjp's blog

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

square869120Contest #2 : G - 道とN個のAtCoder社

考察ゲーで最後まで手こずった。
http://s8pc-2.contest.atcoder.jp/tasks/s8pc_2_g

問題

二次元座標上でN個の点が与えられる。
これらの点を結ぶ線分を何本か配置したとき、線分同士は元の点以外で交差しないようにしたい。
最大何本の線が置けるか。

なお、1直線上に3点以上が存在しないことが保証されている。

解法

自分は全頂点の凸包をベースに以下のように解いた。

まず凸包でN本の線分が引ける。

  • 凸包内に頂点がない、すなわち全頂点が凸包形成に使われている場合:
    • 1つの頂点からN-3頂点に対角線を引くことができるので計2N-3本。
  • 凸包内に頂点がある場合:
    • 凸包を構成する頂点をp個、凸包内の頂点をq個とする。
    • q個のうちどれか1個の頂点から、全凸包のp点にp本の線分を引く。
    • q>1、すなわち他の内部頂点はこの時点でどこかの三角形の内部に入るので、以後三角形の各頂点に3本ずつ線分を引く。
      • 1つの三角形の中に複数頂点が入ることもあるが、1直線上に3点はないので、順に線分を引いて元の凸包を分割していくと、いずれ各頂点は3本ずつ線を引くことになる。
int N;
vector<pair<ll,ll>> V;
ll X[2010],Y[2020];
int did[2020];
template<class C> C veccross(pair<C,C> p1,pair<C,C> p2,pair<C,C> p3) {
	p3.first-=p1.first;p2.first-=p1.first;
	p3.second-=p1.second;p2.second-=p1.second;
	return p3.first*p2.second-p2.first*p3.second;
}

template<class C> vector<int> convex_hull(vector< pair<C, C> >& vp) {
	ll EPS=0;
	vector<pair<pair<C, C>, int> > sorted;
	vector<int> res;
	int i,k=0,rb;
	
	if(vp.size()<=2) {
		if(vp.size()>=1) res.push_back(0);
		if(vp.size()>=2 && vp[0]!=vp[1]) res.push_back(1);
		return res;
	}
	
	FOR(i,vp.size()) sorted.push_back(make_pair(vp[i],i));
	sort(sorted.begin(),sorted.end());
	
	res.resize(vp.size()*2);
	/* bottom */
	FOR(i,vp.size()) {
		while(k>1 && veccross(vp[res[k-2]],vp[res[k-1]],sorted[i].first)<=-EPS) k--;
		res[k++]=sorted[i].second;
	}
	/* top */
	for(rb=k, i=vp.size()-2;i>=0;i--) {
		while(k>rb && veccross(vp[res[k-2]],vp[res[k-1]],sorted[i].first)<=-EPS) k--;
		res[k++]=sorted[i].second;
	}
	res.resize(k-1);
	return res;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		V.push_back({X[i],Y[i]});
	}
	if(N<=1) return _P("0\n");
	if(N<=2) return _P("1\n");
	if(N<=3) return _P("3\n");
	
	auto C=convex_hull(V);
	x=C.size();
	y=N-C.size();
	int ret=x;
	if(y) ret+=x;
	else ret+=x-3;
	if(y>1) ret+=(y-1)*3;
	cout<<ret<<endl;
}

まとめ

最初頑張って図形作ろうかと思ったけど不要だったようだ。