[TIOJ] 1371. 賢狼之網

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

---

裸的凸包，由左至右掃過去維護上凸包跟下凸包，維護方法就是看加入當前這個點是不是在前面兩個所連線的上方(上凸包的話)，如果是就把前一個砍掉，不然就塞進去，下凸包也同理。
不過本題要注意相同高度的點就不用輸出了

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

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