Cod sursa(job #779985)

Utilizator crushackPopescu Silviu crushack Data 19 august 2012 17:11:56
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
#include <algorithm>
#define NMax 120010
using namespace std;

const char IN[]="infasuratoare.in",OUT[]="infasuratoare.out";

struct point{
	double x;
	double y;
	bool operator<(point const &b) const{
		return x<b.x || x==b.x && y<b.y;
	}
} P[NMax] , H[NMax];

int N,L;

double cross(point const &A,point const &B,point const &C){
	return (A.x*(B.y-C.y) + B.x*(C.y-A.y) + C.x*(A.y-B.y))*0.5;
}

void convex(){

	int i,l;
	sort(P+1,P+N+1);
	for (i=1;i<=N;++i){
		while (L>1 && cross(H[L-1],H[L],P[i])<=0)
			--L;
		H[++L]=P[i];
	}
	l=L;
	for (i=N;i>0;--i){
		while (L>l && cross(H[L-1],H[L],P[i])<=0)
			--L;
		H[++L]=P[i];
	}
	--L;
}

int main()
{
	int i;
	freopen(IN,"r",stdin);
	scanf("%d",&N);
	for (i=1;i<=N;++i) scanf("%lf%lf",&P[i].x,&P[i].y);
	fclose(stdin);

	convex();

	freopen(OUT,"w",stdout);
	printf("%d\n",L);
	for (i=1;i<=L;++i) printf("%lf %lf\n",H[i].x,H[i].y);
	fclose(stdout);
	return 0;
}