TopCoder SRM 652 Div2 Hard NoRightTurnDiv2

右に曲がれないと聞いて、自分がyukicoderに投降した奴と似てるかと思ったら違った。
http://community.topcoder.com/stat?c=problem_statement&pm=13644

問題

２次元座標上でN個の頂点の座標が与えられる。
任意の座標から始め、N-1本の線分で全頂点をたどりたい。
その際、自己交差及び右方向に曲がることは許可されない。

条件を満たす頂点の探索順を求めよ。

解法

まず最初の２点は総当たりする。
以後、最後に選んだ２点をp,qとすると、各頂点sに対しとの偏角を比較し、から左回りとなるもののうち最小のsを選んでいく。
最後に、そのような頂点列に対し自己交差がなければ答え。

class NoRightTurnDiv2 {
	public:
	vector<int> X,Y;
	
	bool okok(vector<int> R) {
		int s,t;
		FOR(t,R.size()-1) FOR(s,t-1) {
			ll dx1=X[R[s+1]]-X[R[s]];
			ll dy1=Y[R[s+1]]-Y[R[s]];
			ll dx2=X[R[t]]-X[R[s]];
			ll dy2=Y[R[t]]-Y[R[s]];
			ll dx3=X[R[t+1]]-X[R[s]];
			ll dy3=Y[R[t+1]]-Y[R[s]];
			
			if((((dx1*dy2-dx2*dy1)<0) ^ ((dx1*dy3-dx3*dy1)<0))==0) continue;
			dx1=X[R[t+1]]-X[R[t]];
			dy1=Y[R[t+1]]-Y[R[t]];
			dx2=X[R[s]]-X[R[t]];
			dy2=Y[R[s]]-Y[R[t]];
			dx3=X[R[s+1]]-X[R[t]];
			dy3=Y[R[s+1]]-Y[R[t]];
			if((((dx1*dy2-dx2*dy1)<0) ^ ((dx1*dy3-dx3*dy1)<0))==0) continue;
			return false;
			
		}
		return true;
		
	}
	
	vector <int> findPath(vector <int> x, vector <int> y) {
		X=x, Y=y;
		int N=X.size(),i,s[2];
		double pi=acos(-1);
		
		FOR(s[0],N) FOR(s[1],N) if(s[0]!=s[1]) {
			int vis[60]={};
			int p=s[0], q=s[1];
			
			vis[s[0]]=vis[s[1]]=1;
			vector<int> R;
			R.push_back(s[0]);
			R.push_back(s[1]);
			
			while(R.size()<N) {
				double ang=atan2(Y[q]-Y[p],X[q]-X[p]);
				double mia=pi;
				int id=-1;
				
				FOR(i,N) if(vis[i]==0) {
					double ma=atan2(Y[i]-Y[q],X[i]-X[q])-ang;
					while(ma<0) ma += 2*pi;
					if(ma<mia) mia=ma, id=i;
				}
				if(id==-1) break;
				R.push_back(id);
				vis[id]=1;
				p=q;
				q=id;
			}
			
			if(R.size()==N && okok(R)) return R;
		}
		return vector<int>();
		
	}
}

まとめ

もっと良い解法あるのかな？