Cod sursa(job #304058)

Utilizator hurrycaneBogdan Gaza hurrycane Data 10 aprilie 2009 19:52:48
Problema Infasuratoare convexa Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<cstdio>
#include<math.h>
#include<vector>
#include<cstdlib>
#include<algorithm>

#define EPS 1e-12

using namespace std;

typedef struct{
	double x;
	double y;
	double unghi;
} Punct;


int N;
Punct pmin;
Punct hull[121000];

vector<Punct> S;

int cmpa(const void *a,const void *b){
	Punct c=*(Punct *)a;
	Punct d=*(Punct *)b;

	if(c.unghi<d.unghi) {
		return -1;
	}
	if(c.unghi>d.unghi){
		return 1;
	}
	return 0;
}

int product(Punct A,Punct B,Punct C){
	double sum=(B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
	if(sum<0) return -1;
	else return +1;
}

int main(){
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);

	scanf("%d",&N);

	for(int i=1;i<=N;i++){
		scanf("%lf %lf",&hull[i].x,&hull[i].y);
		if(pmin.y>hull[i].y){
			pmin=hull[i];
		}else if(pmin.y==hull[i].y){
			if(pmin.x<hull[i].x){
				pmin=hull[i];
			}
		}
	}

	for(int i=1;i<=N;i++){
		hull[i].unghi=atan2((hull[i].y)-(pmin.y),(hull[i].x)-(pmin.x));
	}

	qsort(hull,N+1,sizeof(Punct),cmpa);


	S.push_back(hull[1]);
	S.push_back(hull[2]);
	for(int i=3;i<=N;i++){
		while(S.size()>=2 && (product(S[S.size()-2],S[S.size()-1],hull[i])==-1)) S.pop_back();
		S.push_back(hull[i]);
	}
	printf("%ld\n",S.size());
	for(int i=0;i<S.size();i++){
		printf("%lf %lf\n",S[i].x,S[i].y);
	}
	return 0;
}