[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;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology