Cod sursa(job #270787)

Utilizator galacticaBattlestar galactica Data 4 martie 2009 16:52:07
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<stdio.h>
#include<algorithm>
#define PDD pair<double,double>
using namespace std;
int n;
pair <double, double> nr[120010];
int st[120010];
double pantadr;
/*inline int cmp(double a,double b){
	if(a<b)
		return -1;
	if(b<a)
		return 1;
	return 0;
}
int cmpP(const PDD &a,const PDD &b){
	int r=cmp(a.first,b.first);
	if(r)
		return r==-1;
	return cmp(a.second,b.second)==-1;
}*/
bool scot(int a,int b,int c){
	double A=nr[a].second-nr[b].second,B=nr[b].first-nr[a].first,C=nr[a].first*nr[b].second-nr[b].first*nr[a].second;
	if(A*nr[c].first + B*nr[c].second + C<0)
		return true;
	return false;
}
double panta(int i){
	double pp=(nr[i].second-nr[1].second)/(nr[i].first-nr[1].first);
	return pp;
}
void inf(){
	int i=2,vf=2;
	st[1]=1;
	st[2]=2;
	while(i<=n){
		++i;
		if(panta(i)>pantadr)
			continue;
		if(vf>=2 && scot(st[vf-1],st[vf],i))
			--vf;
		st[++vf]=i;
	}
	i=n;
	while(i>1){
		--i;
		if(panta(i)<pantadr)
			continue;
		if(vf>=2 && scot(st[vf-1],st[vf],i))
			--vf;
		st[++vf]=i;
	}
	
	printf("%d\n",vf-1);
	for(i=1;i<vf;++i)
		printf("%.6lf %.6lf\n",nr[st[i]].first,nr[st[i]].second);
}
int main(){
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;++i)
		scanf("%lf%lf",&nr[i].first,&nr[i].second);
	sort(nr+1,nr+n+1);
	pantadr=(nr[1].second-nr[n].second)/(nr[1].first-nr[n].first);
	inf();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}