[TIOJ] 1178. Convex Hull

題目連結:http://tioj.infor.org/problems/1178

---

裸裸的凸包題，不過凸包該如何做呢?可以用掃描線的概念，從左至右掃一遍，試試看某個點會不會是凸包的一部分，試驗方法就是看這個點與相鄰且在暫時凸包的兩個點的夾角，如果大於180則中間那個點將不會是凸包的一部分(可用外積判斷是否大於180)，這樣可求出上凸包，從右至左再掃一遍就可以找到下凸包了XD

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
struct point{
	lld x,y;
	point(lld a,lld b){x=a;y=b;}
};
inline lld cross(point a, point b){
	return a.x*b.y-a.y*b.x;
}
vector<point> dots;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,ans=0;cin>>n;
	for(int i=0;i<n;i++){
		lld a,b;cin>>a>>b;
		dots.push_back(point(a,b));
	}
	vector<point> cHull;
	sort(dots.begin(), dots.end(), [](const point& a, const point& b){return a.x<b.x;});
	for(auto i:dots){
		while(cHull.size()>=2){
			int sz=cHull.size()-1;
			if(cross(point(cHull[sz].x-cHull[sz-1].x,cHull[sz].y-cHull[sz-1].y),\
				point(i.x-cHull[sz-1].x, i.y-cHull[sz-1].y))<0)break;
			cHull.pop_back();
		}
		cHull.push_back(i);
	}
	ans+=cHull.size();
	cHull.clear();
	for(auto i:dots){
		while(cHull.size()>=2){
			int sz=cHull.size()-1;
			if(cross(point(cHull[sz].x-cHull[sz-1].x,cHull[sz].y-cHull[sz-1].y),\
				point(i.x-cHull[sz-1].x, i.y-cHull[sz-1].y))<0)break;
			cHull.pop_back();
		}
		cHull.push_back(i);
	}
	ans+=cHull.size();
	cout<<(ans-2)<<'\n';
	return 0;
}