Cod sursa(job #270832)

Utilizator galacticaBattlestar galactica Data 4 martie 2009 17:26:41
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include<stdio.h>
#include<algorithm>
#define PDD pair<double,double>
#define EPS 1e-12
using namespace std;
int n;
pair <double, double> nr[120010];
int st[120010];
double pantadr;
inline int cmp(double a,double b){
	if(a+EPS<b)
		return -1;
	if(b+EPS<a)
		return 1;
	return 0;
}
int cmpp(const PDD &a,const PDD &b){
	int r=cmp(a.first,b.first);
	if(r!=0)
		return r==-1;
	return cmp(a.second,b.second)==-1;
}
int 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;
	return cmp(A*nr[c].first + B*nr[c].second + C,0);
}
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;
		while(vf>=2 && scot(st[vf-1],st[vf],i)==-1)
			--vf;
		st[++vf]=i;
	}
	i=n;
	while(i>1){
		--i;
		if(panta(i)<pantadr)
			continue;
		while(vf>=2 && scot(st[vf-1],st[vf],i)==-1)
			--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,cmpp);
	pantadr=(nr[n].second-nr[1].second)/(nr[n].first-nr[1].first);
	inf();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}