kmjp's blog

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

Codeforces #559 Div1 D. Winding polygonal line

こちらも考察と実装の割合が程よい問題。
https://codeforces.com/contest/1158/problem/D

問題

2次元座標上でN個の点の座標が与えられる。
3頂点以上が同一直線状に来ることはない。

N個の点を任意の点を始点とし、任意の順で1回ずつ訪問することを考える。
頂点間は直線的に移動し、次の訪問対象の頂点に到達すると、そこで向きを変えその次の訪問対象に向かうとする。

この時、入力として各訪問対象での方向転換が左向きか右向きかの履歴が与えられる。
条件を満たす訪問順を構築せよ。

解法

以下に気が付けば、方針は容易。

  • 次に右向きに回転したいなら、残された未訪問頂点のうち一番左の物を訪問する
  • 次に左向きに回転したいなら、残された未訪問頂点のうち一番右の物を訪問する


そこで、凸包の適当な点を始点にしよう。
次の左右の回転の向きに合わせ、未訪問点のうち上記の条件に従い次の訪問先を貪欲に選べばよい。

int N;
ll X[2020],Y[2020];
string S;
int vis[2020];

ll lef(int a,int b,int c) {
	return (X[b]-X[a])*(Y[c]-Y[a])>(Y[b]-Y[a])*(X[c]-X[a]);
}

void solve() {
	int i,j,k,l,r,x,y;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	cin>>S;
	
	int s=0;
	FOR(i,N) if(X[i]<X[s]) s=i;
	vector<int> V;
	V.push_back(s);
	vis[s]=1;
	FORR(c,S) {
		int cur=V.back();
		int cand=-1;
		FOR(i,N) if(vis[i]==0) {
			if(cand==-1) {
				cand=i;
			}
			else {
				if(lef(cur,cand,i)==(c=='R')) cand=i;
			}
		}
		vis[cand]=1;
		V.push_back(cand);
	}
	FOR(i,N) if(vis[i]==0) V.push_back(i);
	FORR(v,V) cout<<(v+1)<<" ";
	cout<<endl;
	
}

まとめ

こういう軽めの幾何は割と好き。