JOI Open Contest 2012 : B - Jumps

続いて挑戦。
http://joiopen2012.contest.atcoder.jp/tasks/apio_jumps

２次元座標上の点が10万個与えられるので、点同士を直線で結び、全部の点をたどってかつ線同士が交差しない順を回答する。

これはうまく考えると非常に簡単。
まず、全部の点が一直線上にあるときは求める順路が無いので、それで終了。

それ以外の場合、まず点を全部X座標順にソートする。
そして一番左端の点と右端の点を軸とする。

回答は、左端の点をスタートして、軸より上にある点を左端から順に並べていき、終わったら右端の点を通って、今度は軸の下の点を右から順に並べるだけ。
計算量は最初のソートのO(N logN)が最大かな。N=100000だけど何とかいける。

int N;
int X[100001],Y[100001];
int ind[100001];

int online() {
	s64 dx=X[1]-X[0];
	s64 dy=Y[1]-Y[0];
	int i,ol;
	
	ol=0;
	for(i=2;i<N;i++) {
		s64 sx=X[i]-X[0];
		s64 sy=Y[i]-Y[0];
		if(dx*sy==dy*sx) ol++;
	}
	 return (ol==N-2)?1:0;
}

bool pless(const int& l,const int& r) {
	if(X[l]<X[r]) return true;
	if(X[l]==X[r] && Y[l]<Y[r]) return true;
	return false;
}

void solve() {
	int x,y,i,j,ml,mr;
	
	N=GETi();
	FOR(i,N){ GET2(&X[i],&Y[i]); ind[i]=i;}
	
	if(online()) {
		_P("0\n");
		return;
	}
	sort(ind,ind+N,pless);
	
	//1が左上、Nが右下
	_P("%d\n",ind[0]+1);
	
	s64 dx=X[ind[N-1]]-X[ind[0]];
	s64 dy=Y[ind[N-1]]-Y[ind[0]];

	//1-Nの上のある点を左から順に
	for(i=1;i<N-1;i++) {
		s64 sx=X[ind[i]]-X[ind[0]];
		s64 sy=Y[ind[i]]-Y[ind[0]];
		if(sx*dy-sy*dx<=0) _P("%d\n",ind[i]+1);
	}
	
	_P("%d\n",ind[N-1]+1);
	//1-Nの下にある点を右から順に
	for(i=N-2;i>0;i--) {
		s64 sx=X[ind[i]]-X[ind[0]];
		s64 sy=Y[ind[i]]-Y[ind[0]];
		if(sx*dy-sy*dx>0) _P("%d\n",ind[i]+1);
	}
}

まとめ

これはかなり綺麗に解けたと思う。
他の回答を見ると、ソートすらせず軸の上と下の点を列挙しているものがあったけど、入力データはソートされている前提？