Cod sursa(job #418458)

Utilizator swift90Ionut Bogdanescu swift90 Data 15 martie 2010 21:52:21
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 120100
int stiva[N],K;
char fol[N];
struct punct{
	double x,y;
}pct[N];
struct cmp{
	bool operator()(const punct a,const punct b)const{
		if(a.x<b.x)
			return true;
		if(a.x==b.x)
			if(a.y<b.y)
				return true;
		return false;
	}
};
float semn(punct a,punct b,punct c){
	return (a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y));
}
void solve(int n){
	int i;
	K=1;
	fol[0]=1;
	for(i=1;i<n;++i){
		while(K>1 && semn(pct[stiva[K-1]],pct[stiva[K]],pct[i])<0)
			fol[stiva[K--]]=0;
		if(K==1){
			stiva[++K]=i;
			fol[i]=1;
			continue;
		}
		if(semn(pct[stiva[K-1]],pct[stiva[K]],pct[i])>0){
			stiva[++K]=i;
			fol[i]=1;
		}
	}
	for(i=n-1;i>=0;--i){
		if(!fol[i] || !i){
			while(K>1 && semn(pct[stiva[K-1]],pct[stiva[K]],pct[i])<0)
				fol[stiva[K--]]=0;
			if(K==1){
				stiva[++K]=i;
				fol[i]=1;
			}
			if(semn(pct[stiva[K-1]],pct[stiva[K]],pct[i])>0){
				stiva[++K]=i;
				fol[i]=1;
			}
		}
	}
	printf("%d\n",K-1);
	for(i=1;i<K;++i)
		printf("%lf %lf\n",pct[stiva[i]].x,pct[stiva[i]].y);
}
int main(){
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	int n,i;
	scanf("%d",&n);
	for(i=0;i<n;++i)
		scanf("%lf%lf",&pct[i].x,&pct[i].y);
	sort(pct,pct+n,cmp());
	solve(n);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}