アルゴリズム/幾何/凸包走査

青いアリ本には載ってるらしい。
見てみたら自分で書いたのより簡単そうだったのでアレ。
せっかく書いたので置いとこう。
オーダーとか分からない。

#include
#include
#include
#include

using namespace std;

typedef pair<int,int> POINT;

// 外積
int cross(int x1,int y1,int x2,int y2){
	return x1*y2-x2*y1;
}

vector<POINT> pos;

int main(){
	int n,x,y;
	/* input */
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> x >> y;
		pos.push_back(make_pair(x,y));
	}
	/* x座標でソート */
	sort(pos.begin(),pos.end());
	/*上側を走査*/
	int p,q,ans,tmp;
	stack<int> uv,lv;
	uv.push(0);
	uv.push(1);
	for(int i=2;i<pos.size();i++){
		while(1){
			if(uv.size()<2){uv.push(i);break;}
			q=uv.top(); // 取り出す
			uv.pop();
			p=uv.top(); // 取り出さない
			tmp=cross( pos[i].first-pos[p].first, pos[i].second-pos[p].second, pos[q].first-pos[p].first, pos[q].second-pos[p].second);
			if(tmp==0){uv.push(i);break;} // 点Viが直線VpVq上にあるので点Viだけを追加して次へ
			else if(tmp>0){uv.push(q);uv.push(i);break;} // 点Viが直線VpVqより内側なので点Vqを戻し、点Viを追加して次へ
			// 点Viが直線VpVqより外側にあったので点Vqを削除し、続行
		}
	}
	/*下側を走査*/ // 同じ処理してるし関数化してもいいのでは
	lv.push(0);
	lv.push(1);
	for(int i=2;i<pos.size();i++){
		while(1){
			if(lv.size()<2){lv.push(i);break;}
			q=lv.top();
			lv.pop(); // 取り出す
			p=lv.top(); // 取り出さない
			tmp=cross( pos[i].first-pos[p].first, pos[i].second-pos[p].second, pos[q].first-pos[p].first, pos[q].second-pos[p].second );
			if(tmp==0){lv.push(i);break;} // 点Viが直線VpVq上にあるので点Viだけを追加して次へ
			else if(tmp<0){lv.push(q);lv.push(i);break;} // 点Viが直線VpVqより内側なので点Vqを戻し、点Viを追加して次へ
			// 点Viが直線VpVqより外側にあったので点Vqを削除し、続行
		}
	}
	ans=uv.size()+lv.size()-2; // 重複分を引く (始点と終点)
	/* output */
	cout << ans << endl;

	return 0;
}